Skip to content
RSS feed tkhwang on GitHub tkhwang on Twitter

🔥 Sliding window algorithm in javascript

✨ Background 

[0,                     ...                  , N-1]
      [ left,           ... , right ]
      => shrink window               => expand window
         if condition is NOT OK
  • The idea behind the sliding window technique is to efficiently find the "best" window that fits some constraint.
  • Usually used for solving subarray (continuous array) problems.
  • Efficiently find the "best" window that fits some constraint.

🔥 Algorithm

  • When right moves, which data should be updated ?
  • When should the window be shrinked ?
  • When left moves, which data should be updated ?
  • Where should we update the result : expanding or shrinking ?
const needs = {};
const window = {};

let left = 0;
for (let right = 0; right < N; right += 1) {
  // update window information

  while (WINDOW_CONDITION_BROKEN) {
    // remove/reduce arr[left] information in window
    left += 1;
  }

  // check whether window meets needs condition
}

🗒️ Typical problems

List

Medium

🏷️ Related tags

📚 References