Sliding window: a stretch that moves along the array

Look at one contiguous stretch of the array at a time, and update its total as it moves: add the element entering on the right, remove the element leaving on the left. Never re-add the whole stretch.

Think of it like this: a caterpillar crawling along a branch. Its front end reaches forward, and its back end catches up. It never jumps back to the start of the branch.

What a window is

Fixed-size windows

function movingAverages(readings: number[], k: number): number[] {
  const out: number[] = [];
  let sum = 0;
  for (let right = 0; right < readings.length; right++) {
    sum += readings[right];                  // element entering on the right
    if (right >= k) sum -= readings[right - k]; // element leaving on the left
    if (right >= k - 1) out.push(sum / k);   // window is full: record it
  }
  return out;
}

Variable-size windows: grow right, shrink left

How to spot it

Words and constraints in a problem that point to this pattern:

• “Contiguous subarray” or “substring”, together with “longest”, “shortest”, “maximum” or “minimum”
• “Every window of size k”, “k consecutive days”, “in any stretch of k”
• “At most k …”, “no more than k distinct / zeros / repeats”
• “Without repeating characters”, “containing all of …”
• A brute force that recomputes almost the same range for every start position

Watch it work

The template

// Fixed size k: add the newcomer, drop the leaver
function fixedWindow(nums: number[], k: number): void {
  let sum = 0;                              // total of the current window
  for (let right = 0; right < nums.length; right++) {
    sum += nums[right];                     // element entering the window
    if (right >= k) sum -= nums[right - k]; // element that has left the window
    if (right >= k - 1) {                   // window nums[right-k+1 .. right] is full
      // use sum here: compare it with a best, store it, check a rule...
    }
  }
}

// Variable size, "longest valid": grow right, shrink left while invalid
function longestValid(nums: number[], limit: number): number {
  let left = 0;                             // start of the window
  let state = 0;                            // running info: a sum, a count, a Map...
  let best = 0;
  for (let right = 0; right < nums.length; right++) {
    state += nums[right];                   // 1. grow: take in nums[right]
    while (/* window is invalid */ state > limit) {
      state -= nums[left];                  // 2. shrink: undo nums[left]
      left++;                               //    and move the start forward
    }
    best = Math.max(best, right - left + 1); // 3. window is valid: record it
  }
  return best;
}

Worked example

1. Brute force: try every start, extend to every end, and count the zeros. If the count is at most k, record the length. Even counting zeros as you extend, that's two nested loops: O(n²). With 100,000 days, 10 billion steps.

   let best = 0;
   for (let start = 0; start < days.length; start++) {
     let zeros = 0;
     for (let end = start; end < days.length; end++) {
       if (days[end] === 0) zeros++;
       if (zeros > k) break;
       best = Math.max(best, end - start + 1);
     }
   }
   

2. Spot the waste. When the start moves from 0 to 1, the inner loop recounts all the same days again. Only one day left the stretch. Also notice the words: longest stretch, contiguous days, at most k. That's a variable-size window.

3. Decide the state and the rule. State: zeros, the number of 0s inside the window. Rule: the window is valid while zeros <= k. Adding a 0 can only break the rule, and removing a 0 can only fix it, so grow-and-shrink works.

4. Fill in the template. Grow: if the new day is 0, zeros++. Shrink while zeros > k: if the day leaving is 0, zeros--, then left++. Record the length.

   function longestUpStretch(days: number[], k: number): number {
     let left = 0;
     let zeros = 0;
     let best = 0;
     for (let right = 0; right < days.length; right++) {
       if (days[right] === 0) zeros++;
       while (zeros > k) {
         if (days[left] === 0) zeros--;
         left++;
       }
       best = Math.max(best, right - left + 1);
     }
     return best;
   }
   

5. Check it on the example. right grows to index 4 with one zero inside: [1, 1, 0, 1, 1], length 5. At index 5 a second 0 arrives, so zeros = 2. Shrink: left steps past index 0 and 1 (both 1s, zeros unchanged), then past the 0 at index 2, so zeros = 1 and left = 3. The window then grows to the end: indexes 3 to 8, length 6. Edge cases: k = 0 gives the longest run of 1s. All 1s gives the full length. An empty array gives 0.

Common mistakes

• Off by one in the length: writing right - left instead of right - left + 1. Every answer comes out 1 too small.
• Using if instead of while to shrink. One removal may not be enough to make the window valid, so an invalid window gets recorded and the answer is too big.
• Recording before shrinking in a "longest" problem. You count a window that breaks the rule.
• Forgetting to undo nums[left] from the state before moving left. The sum or count drifts, and the window looks invalid forever.
• Using grow-and-shrink when the array has negative numbers and the rule is about the sum. Removing an element can then raise the sum, so shrinking doesn't fix the window and answers are wrong.

Cost

In interviews