DAY 5 / 30 · WEEK 1

Sliding Window Pattern

Goal of the day

• Recognize sliding-window problems: anything about a contiguous subarray or substring.
• Implement both shapes: a fixed-size window and a variable-size (expand/shrink) window.
• Turn a brute-force O(n·k) or O(n²) rescan into a single O(n) pass.

Concept

Imagine looking at a strip of numbers through a physical window frame that only shows 3 at a time. The brute-force way to find, say, the maximum 3-number sum: slide the frame one step, then re-add all 3 numbers you can see — O(k) work per slide, O(n·k) total. The sliding-window trick: when you slide the frame right by one, you already know the sum inside it — you just subtract the number that left on the left edge and add the number that entered on the right edge. One subtraction, one addition, O(1) per slide, O(n) total. You never recompute from scratch.

That's a fixed-size window. A variable-size window works the same "track what enters and leaves" idea, but the frame itself grows and shrinks: you expand the right edge to bring in new elements, and whenever the window breaks some rule (too big a sum, a repeated character), you shrink from the left edge until it's valid again. Both shapes share the same core move: two pointers marking the window's edges, and O(1) bookkeeping — not a full rescan — every time either edge moves.

Diagrams

1. Fixed-size window (size 3)

2. Variable-size window (expand / shrink)

Interactive visualizations

1. Maximum sum subarray of size k

2. Longest substring without repeating characters

The code

// --- Shape 1: fixed-size window ---
function maxSumSubarray(arr, k) {
  let windowSum = 0;
  for (let i = 0; i < k; i++) windowSum += arr[i]; // build the first window once
  let best = windowSum;
  for (let i = k; i < arr.length; i++) {
    windowSum += arr[i] - arr[i - k]; // add entering, subtract leaving
    best = Math.max(best, windowSum);
  }
  return best;
}

// --- Shape 2: variable-size window ---
function lengthOfLongestSubstring(s) {
  const seen = new Set();
  let left = 0, best = 0;
  for (let right = 0; right < s.length; right++) {
    while (seen.has(s[right])) {       // shrink until the duplicate is gone
      seen.delete(s[left]);
      left++;
    }
    seen.add(s[right]);                // now safe to include s[right]
    best = Math.max(best, right - left + 1);
  }
  return best;
}

Line by line:

• maxSumSubarray — the first loop builds the initial window's sum once (O(k)). Every loop after that does exactly one add and one subtract — O(1) each — instead of re-summing k elements.
• lengthOfLongestSubstring — right always moves forward, one step per outer-loop iteration. The while loop shrinks left (possibly zero times, possibly several) until the window contains no duplicate of s[right]. Because left only ever moves forward too, it can advance at most n times total across the entire function — that's what keeps this O(n) instead of O(n²), even though there's a loop inside a loop.

Dry run: maxSumSubarray([4, 2, 5, 1, 3], k = 3)

The best 3-element window is the very first one, [4, 2, 5] = 11 — found in one O(k) setup pass plus two O(1) slides, instead of three separate O(k) resums.

Complexity

Interview corner

• How do you recognize a sliding-window problem? The problem asks about a contiguous subarray or substring — a maximum/minimum sum, a length, or "does a window satisfy some property" (no repeats, sum ≤ target, at most k distinct characters). If it's about non-contiguous subsequences, sliding window doesn't apply — look at DP instead (Week 4).
• Fixed vs. variable window — how do you tell which one a problem needs? If the window size is given directly ("subarray of size k"), it's fixed. If you're optimizing the window size itself ("longest/shortest subarray such that..."), it's variable.
  ↳ Common follow-up: "Can you do this with O(1) extra space instead of a Set/Map?" — sometimes, if the constraint is purely numeric (e.g. a running sum), but character/frequency constraints usually need the tracking structure.
• What's the most common sliding-window bug? Forgetting to shrink the window fully before re-measuring it, or shrinking by a fixed amount instead of by a while loop.
  ⚠ Trap: using if instead of while to shrink only shrinks by one step — if the window is invalid by more than one element, an if leaves it still invalid. Always shrink with a loop that re-checks the condition.
• What if k is bigger than the array's length? There's no valid fixed-size window at all — decide (and say out loud) whether that should return 0, -Infinity, or throw, based on what the problem specifies.

How to talk through it out loud: name the window's invariant before coding — "I'll expand right to grow the window, and shrink left with a while loop any time the window has a duplicate, so at every point after the inner loop the window is valid." Stating the invariant is what proves to an interviewer you're not just pattern-matching syntax you memorized.

Practice problems

function findMaxAverage(nums, k) {
  let windowSum = 0;
  for (let i = 0; i < k; i++) windowSum += nums[i];
  let best = windowSum;
  for (let i = k; i < nums.length; i++) {
    windowSum += nums[i] - nums[i - k];
    best = Math.max(best, windowSum);
  }
  return best / k;
}

function minSubArrayLen(target, nums) {
  let left = 0, sum = 0, best = Infinity;
  for (let right = 0; right < nums.length; right++) {
    sum += nums[right];
    while (sum >= target) {
      best = Math.min(best, right - left + 1);
      sum -= nums[left];
      left++;
    }
  }
  return best === Infinity ? 0 : best;
}

function lengthOfLongestSubstring(s) {
  const seen = new Set();
  let left = 0, best = 0;
  for (let right = 0; right < s.length; right++) {
    while (seen.has(s[right])) {
      seen.delete(s[left]);
      left++;
    }
    seen.add(s[right]);
    best = Math.max(best, right - left + 1);
  }
  return best;
}

Quiz