🪟 Sliding Window

A learning sheet — turn O(n²) subarray scans into one linear pass by reusing the window you already built.

🧠 1 · How to think (and invent it)

The one idea: a contiguous sub-array/sub-string answer depends on a window [left, right]. Instead of rebuilding every window from scratch (O(n²)), slide: when right moves one step, you only add one element; when you must shrink, left only ever moves forward. Each index enters and leaves the window once ⇒ O(n).

The whole topic is one question: "when is my window valid, and which end do I move to fix it?" Answer that with an invariant and the template writes itself.

Watch it get invented — Longest Substring Without Repeating Characters

1. Start brute. Check every substring for uniqueness → O(n²) or worse.
2. Spot the waste. If [left, right] has no repeat and you push right, you don't re-scan the whole thing — you only need to know if the new char already sits in the window. And when it does, sliding left backward is pointless: any earlier start contains the duplicate too. left only moves forward.
3. The leap. Keep lastSeen[char]. On each right, jump left to max(left, lastSeen[c] + 1) — past the previous copy. Record right − left + 1.
4. Payoff. Each index is visited by right once and by left once ⇒ O(n).

Input "abcabcbb" → answer 3. Watch left jump forward on each repeat, never back.

🎯 2 · Attack plan

🔎 3 · Recognition map

🧩 4 · The five core patterns

Each = a one-line model, a 🔑 invariant, a template, a picture, and a 🎤 interview lens. The two variable templates differ in one line — where you record the answer.

4.1 · Fixed window — size k

“Add the newcomer, drop the one that fell off the back.”

Setup: maintain a running window state for exactly k elements. Each step is O(1): add a[right], and once the window is full, subtract a[right−k].

// Maximum sum of any size-k subarray
function maxSumK(a: number[], k: number): number {
  let sum = 0, best = -Infinity;
  for (let right = 0; right < a.length; right++) {
    sum += a[right];                 // add newcomer
    if (right >= k) sum -= a[right - k];  // drop the one that fell off
    if (right >= k - 1) best = Math.max(best, sum); // window is full
  }
  return best;
}

4.2 · Variable window — longest valid

“Grow greedily; shrink only while broken; measure after.”

Setup: expand right every step. If the window became invalid, shrink from left until it's valid again — then record the length.

// Longest substring with at most K distinct characters
function longestKDistinct(s: string, k: number): number {
  const count = new Map<string, number>();
  let left = 0, best = 0;
  for (let right = 0; right < s.length; right++) {
    count.set(s[right], (count.get(s[right]) ?? 0) + 1);  // grow
    while (count.size > k) {                               // shrink WHILE invalid
      const c = s[left++];
      const n = count.get(c)! - 1;
      if (n === 0) count.delete(c); else count.set(c, n);
    }
    best = Math.max(best, right - left + 1);               // record (now valid)
  }
  return best;
}

4.3 · Variable window — shortest valid

“Grow until valid; then squeeze as much as it stays valid.”

Setup: mirror of 4.2. Expand until the window is valid; then shrink from left while still valid, recording the length during the shrink.

// Minimum Size Subarray Sum ≥ target  (positives only)
function minSubArrayLen(target: number, a: number[]): number {
  let left = 0, sum = 0, best = Infinity;
  for (let right = 0; right < a.length; right++) {
    sum += a[right];
    while (sum >= target) {                       // shrink WHILE valid
      best = Math.min(best, right - left + 1);    // record DURING
      sum -= a[left++];
    }
  }
  return best === Infinity ? 0 : best;
}

The one-line difference vs §4.2: longest shrinks while invalid and records after; shortest shrinks while valid and records during. Same skeleton, opposite trigger.

4.4 · Counting — "exactly K" via "at most K"

“You can't window ‘exactly’; window ‘at most’ twice and subtract.”

Why: "exactly K" isn't monotonic (a valid window can become invalid and valid again as you grow), so a single window can't count it. But "at most K" is monotonic. So: exactly(K) = atMost(K) − atMost(K−1).

// Subarrays with exactly K distinct integers
function subarraysKDistinct(a: number[], k: number): number {
  const atMost = (k: number): number => {
    if (k < 0) return 0;
    const count = new Map<number, number>();
    let left = 0, res = 0;
    for (let right = 0; right < a.length; right++) {
      count.set(a[right], (count.get(a[right]) ?? 0) + 1);
      while (count.size > k) {
        const n = count.get(a[left])! - 1;
        if (n === 0) count.delete(a[left]); else count.set(a[left], n);
        left++;
      }
      res += right - left + 1;      // # of valid subarrays ending at right
    }
    return res;
  };
  return atMost(k) - atMost(k - 1);
}

4.5 · Monotonic deque — max/min in each window

“Keep a deque of candidates in decreasing order; the front is the answer.”

Setup: store indices in a deque whose values are strictly decreasing. The front is always the window max. Pop the back while it's ≤ the newcomer (it can never be the max again); pop the front when it slides out of the window.

// Sliding Window Maximum — max of every size-k window
function maxSlidingWindow(a: number[], k: number): number[] {
  const dq: number[] = [];   // indices; a[dq] strictly decreasing
  let head = 0;               // ⭐ head pointer — never shift(), O(1) evict
  const res: number[] = [];
  for (let i = 0; i < a.length; i++) {
    while (dq.length > head && a[dq[dq.length - 1]] <= a[i]) dq.pop();  // keep decreasing
    dq.push(i);
    if (dq[head] <= i - k) head++;          // evict out-of-window front — O(1), no shift
    if (i >= k - 1) res.push(a[dq[head]]);  // front = current max
  }
  return res;
}

⏱️ 5 · Complexity

⚠️ 6 · Pitfalls — and the test that catches each

// 560 Subarray Sum Equals K — NEGATIVES break the window → prefix sums + counts
function subarraySum(nums: number[], k: number): number {
  const freq = new Map<number, number>([[0, 1]]);        // empty prefix, so subarrays starting at 0 count
  let sum = 0, count = 0;
  for (const x of nums) {
    sum += x;
    count += freq.get(sum - k) ?? 0;                     // earlier prefixes that leave exactly k
    freq.set(sum, (freq.get(sum) ?? 0) + 1);             // insert AFTER the lookup
  }
  return count;
}

// 219 Contains Duplicate II — fixed window of the last k values
function containsNearbyDuplicate(nums: number[], k: number): boolean {
  const win = new Set<number>();
  for (let i = 0; i < nums.length; i++) {
    if (win.has(nums[i])) return true;
    win.add(nums[i]);
    if (win.size > k) win.delete(nums[i - k]);           // evict AFTER adding
  }
  return false;
}

📊 Coverage — pattern → LeetCode (medium & hard)

Own each pattern and these are in range. Bold = Hard tier.

✅ 7 · Self-check

Cover the right column (blurred — hover/tap to reveal). Say your answer out loud first.

Write these cold (no peeking)

• fixed maxSumK and anagram-in-string (26-freq match)
• longest longestKDistinct + the replacement-trap variant
• shortest minSubArrayLen and minimum-window-substring
• counting subarraysKDistinct via atMost
• deque maxSlidingWindow

For each: write the validity condition and where you record the answer as a comment first, then the loop.