Chapter 6 — Sliding Window

Two pointers converge. Sliding window expands and contracts.
Both are O(n). The difference is what you're optimizing.

Part 1: The Problem That Breaks Brute Force

Problem: Find the maximum sum of any contiguous subarray of length k.
maxSum([2,1,5,1,3,2], k=3) → 9 (subarray [5,1,3])

Brute force: for every starting position, sum the next k elements.

javascript

function maxSum(nums, k) {
  let max = -Infinity;
  for (let i = 0; i <= nums.length - k; i++) {
    let sum = 0;
    for (let j = i; j < i + k; j++) {
      sum += nums[j];
    }
    max = Math.max(max, sum);
  }
  return max;
}

For array of length n with window size k: O(n × k). For n=100,000 and k=1,000: 100 million operations.

Where is the waste?

When we slide from window [i, i+k-1] to window [i+1, i+k], we recompute the entire sum. But the two windows share k-1 elements. We're computing the sum of those k-1 elements twice.

The fix: when sliding one step right, subtract the element that left the window, add the element that entered. One subtraction, one addition — O(1) per slide.

This is sliding window.

Part 2: What Sliding Window Is

A window is a contiguous range [left, right] in an array or string. At any moment, the window has a size (right - left + 1) and a state (some property computed over the elements in range — their sum, the set of distinct characters, the count of a particular value, etc.).

The window slides by:

Expanding right: include arr[right], update state, advance right.
Shrinking left: remove arr[left], update state, advance left.

The critical insight: Each element enters the window exactly once (when right reaches it) and leaves the window exactly once (when left passes it). Total work: 2n operations = O(n), regardless of window size.

Two variants:

Fixed-size window: k is given. Window always has exactly k elements. Slide one step: shrink left, expand right.

Variable-size window: Window expands until a constraint is violated, then shrinks until valid again. You're finding the maximum or minimum window satisfying a condition.

Part 3: Fixed-Size Window — The Template

code

Initialize: compute state for the first k elements.
Slide: for i from k to n-1:
  - Add arr[i] to state (new right element).
  - Remove arr[i - k] from state (old left element, now outside window).
  - Update answer from current state.

Maximum sum, k=3, step by step:

javascript

function maxSumWindow(nums, k) {
  let windowSum = 0;

  // Initialize first window
  for (let i = 0; i < k; i++) {
    windowSum += nums[i];
  }

  let max = windowSum;

  // Slide
  for (let i = k; i < nums.length; i++) {
    windowSum += nums[i];       // add incoming right element
    windowSum -= nums[i - k];   // remove outgoing left element
    max = Math.max(max, windowSum);
  }

  return max;
}

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

code

Init: windowSum = 2+1+5 = 8. max=8.

i=3: +nums[3]=1, -nums[0]=2. windowSum=8+1-2=7. max=8.
i=4: +nums[4]=3, -nums[1]=1. windowSum=7+3-1=9. max=9.
i=5: +nums[5]=2, -nums[2]=5. windowSum=9+2-5=6. max=9.

return 9. ✓ (window [5,1,3])

Complexity: O(n) time (one pass), O(1) space.

Part 4: Variable-Size Window — The Expand/Contract Template

For problems where the optimal window size is unknown, we use a two-pointer window that expands and contracts based on a condition.

The template:

code

left = 0
for right from 0 to n-1:
  add arr[right] to window state

  while window violates constraint:
    remove arr[left] from state
    left++

  update answer (window [left, right] now satisfies constraint)

Why this is O(n):

right advances n times total.
left also advances at most n times total (it never goes backward).
Total pointer moves: ≤ 2n. Each move does O(1) or O(log n) work (depending on data structure).

The key design question: What is the constraint? When is the window valid? When is it violated?

"Longest substring with at most k distinct characters" → violated when distinct count > k.
"Minimum window containing all target characters" → valid when all targets are covered.
"Longest subarray with sum ≤ k" → violated when sum > k.

Part 5: Variable-Size Window — Longest Substring Without Repeating Characters

Problem: Find the length of the longest substring without repeating characters.
lengthOfLongestSubstring("abcabcbb") → 3 ("abc")
LeetCode 3. Most-asked sliding window problem globally.

Constraint: No character appears more than once in [left, right].
State: A Set (or frequency map) of characters in the current window.
When violated: When arr[right] is already in the window.

javascript

function lengthOfLongestSubstring(s) {
  let left = 0;
  let max = 0;
  const seen = new Set();

  for (let right = 0; right < s.length; right++) {
    // Window violated: s[right] already in window
    while (seen.has(s[right])) {
      seen.delete(s[left]);  // shrink from left
      left++;
    }

    seen.add(s[right]);
    max = Math.max(max, right - left + 1);
  }

  return max;
}

Dry run: lengthOfLongestSubstring("abcabcbb")

code

left=0, seen={}, max=0.

right=0 'a': 'a' not in seen. seen={a}. max=1. window=[0,0] "a".
right=1 'b': 'b' not in seen. seen={a,b}. max=2. window=[0,1] "ab".
right=2 'c': 'c' not in seen. seen={a,b,c}. max=3. window=[0,2] "abc".
right=3 'a': 'a' IN seen.
  → delete s[0]='a', left=1. seen={b,c}.
  'a' not in seen now. seen={b,c,a}. max=3. window=[1,3] "bca".
right=4 'b': 'b' IN seen.
  → delete s[1]='b', left=2. seen={c,a}.
  'b' not in seen now. seen={c,a,b}. max=3. window=[2,4] "cab".
right=5 'c': 'c' IN seen.
  → delete s[2]='c', left=3. seen={a,b}.
  'c' not in seen now. seen={a,b,c}. max=3. window=[3,5] "abc".
right=6 'b': 'b' IN seen.
  → delete s[3]='a', left=4. seen={b,c}.   (deleted 'a', but 'b' still in seen)
  → delete s[4]='b', left=5. seen={c}.
  'b' not in seen now. seen={c,b}. max=3. window=[5,6] "cb".
right=7 'b': 'b' IN seen.
  → delete s[5]='c', left=6. seen={b}.
  → delete s[6]='b', left=7. seen={}.
  'b' not in seen now. seen={b}. max=3. window=[7,7] "b".

return 3. ✓

Why while not if? When s[right] is a duplicate, we must keep shrinking until the duplicate is evicted. Multiple elements may be removed before the window is valid again (e.g., step at right=6 where two elements were removed).

Optimization with HashMap (O(1) jump):
Instead of a Set and while loop, store the last seen index of each character. When s[right] is a duplicate at index prev, jump left directly to prev + 1 — no inner while loop needed.

javascript

function lengthOfLongestSubstringOpt(s) {
  const lastSeen = new Map();
  let left = 0, max = 0;

  for (let right = 0; right < s.length; right++) {
    if (lastSeen.has(s[right]) && lastSeen.get(s[right]) >= left) {
      left = lastSeen.get(s[right]) + 1;  // jump past the duplicate
    }
    lastSeen.set(s[right], right);
    max = Math.max(max, right - left + 1);
  }

  return max;
}

The >= left check is critical: if we saw s[right] before, but at an index to the left of our current window, it doesn't matter — it's not in the current window. Only update left if the previous occurrence is inside the window.

Part 6: Variable-Size Window — Minimum Window Substring

Problem: Given string s and string t, find the minimum window in s containing all characters of t.
minWindow("ADOBECODEBANC", "ABC") → "BANC"
LeetCode 76. Hard. Asked at Google, Meta, Amazon.

Constraint: Window must contain every character in t (with correct frequencies).
Valid window: have === need (all required characters satisfied).
Strategy: Expand until valid, then shrink to minimize, record answer, shrink one more, repeat.

javascript

function minWindow(s, t) {
  if (t.length === 0) return "";

  // Count required characters
  const need = new Map();
  for (const c of t) need.set(c, (need.get(c) ?? 0) + 1);

  // Count what we currently have in window
  const have_map = new Map();
  let have = 0;           // distinct character types satisfied
  const need_count = need.size;  // distinct character types required

  let result = "";
  let minLen = Infinity;
  let left = 0;

  for (let right = 0; right < s.length; right++) {
    const c = s[right];
    have_map.set(c, (have_map.get(c) ?? 0) + 1);

    // Check if this character's requirement is now satisfied
    if (need.has(c) && have_map.get(c) === need.get(c)) {
      have++;
    }

    // While window is valid, try to shrink from left
    while (have === need_count) {
      // This window is valid — record if minimum
      if (right - left + 1 < minLen) {
        minLen = right - left + 1;
        result = s.slice(left, right + 1);
      }

      // Shrink left
      const leftChar = s[left];
      have_map.set(leftChar, have_map.get(leftChar) - 1);
      if (need.has(leftChar) && have_map.get(leftChar) < need.get(leftChar)) {
        have--;  // this required character is now under-satisfied
      }
      left++;
    }
  }

  return result;
}

Dry run: minWindow("ADOBECODEBANC", "ABC")

need = {A:1, B:1, C:1}, need_count = 3, have = 0.

code

right=0 'A': have_map={A:1}. A satisfied (1===1). have=1.
right=1 'D': have_map={A:1,D:1}. D not in need. have=1.
right=2 'O': have_map={...,O:1}. have=1.
right=3 'B': have_map={...,B:1}. B satisfied. have=2.
right=4 'E': have=2.
right=5 'C': have_map={...,C:1}. C satisfied. have=3.

have===need_count=3. Window valid! [0,5] = "ADOBEC". len=6. result="ADOBEC".
  Shrink: remove s[0]='A'. have_map[A]=0. A unsatisfied (0 < 1). have=2. left=1.
  have=2 < 3. Stop shrinking.

right=6 'O': have=2.
right=7 'D': have=2.
right=8 'E': have=2.
right=9 'B': have_map[B]=2. B was already satisfied (2>1). have stays 2.
right=10 'A': have_map[A]=1. A satisfied (1===1). have=3.

have===3. Window [1,10]="DOBECODEBA". len=10. No improvement.
  Shrink: remove s[1]='D'. D not in need. have=3. left=2.
  have===3. Window [2,10]="OBECODEBA". len=9. No improvement.
  Shrink: remove s[2]='O'. not in need. have=3. left=3.
  Window [3,10]="BECODEBA". len=8. No improvement.
  Shrink: remove s[3]='B'. have_map[B]=1. B still satisfied (1>=1). have=3. left=4.
  Window [4,10]="ECODEBA". len=7. No improvement.
  Shrink: remove s[4]='E'. not in need. left=5.
  Window [5,10]="CODEBA". len=6. No improvement (equal, not less).
  Shrink: remove s[5]='C'. have_map[C]=0. C unsatisfied. have=2. left=6.
  have=2. Stop shrinking.

right=11 'N': have=2.
right=12 'C': have_map[C]=1. C satisfied. have=3.

have===3. Window [6,12]="ODEBANC". len=7. No improvement.
  Shrink: remove s[6]='O'. not in need. left=7.
  Window [7,12]="DEBANC". len=6. No improvement.
  Shrink: remove s[7]='D'. not in need. left=8.
  Window [8,12]="EBANC". len=5. No improvement.
  Shrink: remove s[8]='E'. not in need. left=9.
  Window [9,12]="BANC". len=4 < 6. result="BANC". minLen=4.
  Shrink: remove s[9]='B'. have_map[B]=0. B unsatisfied. have=2. left=10.
  have=2. Stop shrinking.

right=13: out of bounds. Loop ends.

return "BANC". ✓

Complexity: O(|s| + |t|) time — each character in s is added once and removed once. O(|t|) space for the frequency maps.

Why have tracks count of satisfied character types (not total characters): We need all k distinct character types in t to each be satisfied. Tracking have === need.size is a single comparison. If we tracked total characters satisfied, we'd need to distinguish between "character A appeared once (satisfying it)" and "character A appeared twice (still satisfies but more than needed)".

Part 7: Variable-Size Window — Minimum Size Subarray Sum

Problem: Find the minimum length subarray with sum ≥ target.
minSubArrayLen(7, [2,3,1,2,4,3]) → 2 (subarray [4,3])
LeetCode 209.

Constraint: sum >= target.
When violated: sum < target — expand.
When valid: sum >= target — record length, shrink to minimize.

javascript

function minSubArrayLen(target, nums) {
  let left = 0, sum = 0, min = Infinity;

  for (let right = 0; right < nums.length; right++) {
    sum += nums[right];

    while (sum >= target) {
      min = Math.min(min, right - left + 1);
      sum -= nums[left];
      left++;
    }
  }

  return min === Infinity ? 0 : min;
}

Dry run: minSubArrayLen(7, [2,3,1,2,4,3])

code

left=0, sum=0, min=∞.

right=0: sum=2. 2<7.
right=1: sum=5. 5<7.
right=2: sum=6. 6<7.
right=3: sum=8. 8>=7!
  min=min(∞,3-0+1)=4. sum=8-2=6. left=1.
  6<7. Stop shrinking.
right=4: sum=6+4=10. 10>=7!
  min=min(4,4-1+1)=4. sum=10-3=7. left=2.
  7>=7!
  min=min(4,4-2+1)=3. sum=7-1=6. left=3.
  6<7. Stop shrinking.
right=5: sum=6+3=9. 9>=7!
  min=min(3,5-3+1)=3. sum=9-2=7. left=4.
  7>=7!
  min=min(3,5-4+1)=2. sum=7-4=3. left=5.
  3<7. Stop shrinking.

return 2. ✓ (subarray [4,3])

Part 8: Fixed Window With HashMap — Permutation in String

Problem: Return true if any permutation of string p exists as a substring of s.
checkInclusion("ab", "eidbaooo") → true ("ba" at index 3)
LeetCode 567.

A permutation of p in s means: some window of length p.length in s has exactly the same character frequencies as p.

State: Frequency map of characters in the current window.
Equality check: Window's frequency map matches p's frequency map.

To check equality efficiently: track matches — the count of characters whose frequency in the window equals their frequency in p. When matches === 26 (all characters match), we have a permutation.

javascript

function checkInclusion(p, s) {
  if (p.length > s.length) return false;

  const pCount = new Array(26).fill(0);
  const wCount = new Array(26).fill(0);
  const a = 'a'.charCodeAt(0);

  // Count p's frequencies
  for (const c of p) pCount[c.charCodeAt(0) - a]++;

  // Initialize first window
  for (let i = 0; i < p.length; i++) wCount[s.charCodeAt(i) - a]++;

  // Count how many characters match between window and p
  let matches = 0;
  for (let i = 0; i < 26; i++) {
    if (pCount[i] === wCount[i]) matches++;
  }

  if (matches === 26) return true;

  // Slide window
  for (let right = p.length; right < s.length; right++) {
    const left = right - p.length;

    // Add right character
    const rIdx = s.charCodeAt(right) - a;
    wCount[rIdx]++;
    if (wCount[rIdx] === pCount[rIdx]) matches++;
    else if (wCount[rIdx] === pCount[rIdx] + 1) matches--;  // was matching, now over

    // Remove left character
    const lIdx = s.charCodeAt(left) - a;
    wCount[lIdx]--;
    if (wCount[lIdx] === pCount[lIdx]) matches++;
    else if (wCount[lIdx] === pCount[lIdx] - 1) matches--;  // was matching, now under

    if (matches === 26) return true;
  }

  return false;
}

Dry run: checkInclusion("ab", "eidbaooo")

code

p="ab". pCount[a]=1, pCount[b]=1. All others 0.

First window "ei": wCount[e]=1, wCount[i]=1.
matches: a:0≠1, b:0≠1, e:1≠0... wait.
pCount[e]=0, wCount[e]=1: no match. For all 24 chars where both are 0: match. matches=24.
(a doesn't match: p=1, w=0. b doesn't match: p=1, w=0. matches=24.)

matches=24≠26.

right=2 'd' (idx=3), left=0 'e' (idx=4):
  Add 'd': wCount[d]=1. pCount[d]=0. 1≠0. was 0=0 (match) → now 1≠0: matches=23.
  Remove 'e': wCount[e]=0. pCount[e]=0. 0=0: matches=24.
right=3 'b', left=1 'i':
  Add 'b': wCount[b]=1. pCount[b]=1. match! matches=25.
  Remove 'i': wCount[i]=0. pCount[i]=0. match! matches=26.
  return true. ✓ (window "db"... wait)

Hmm, let me recheck. Window at right=3: [left=1, right=3] = s[1..3] = "idb". That's 3 characters but p.length=2, so left = right - p.length = 3 - 2 = 1. Window = s[1..3) = s[1] to s[2] (2 chars) = "id". But right=3 is 'b'...

Let me re-trace more carefully.

Actually the slide loop: right goes from p.length=2 to s.length-1=7. When right=2 (which is s[2]='d'), left = right - p.length = 2-2 = 0. So we add s[2]='d' and remove s[0]='e'. Window becomes s[1..2] = "id".

When right=3 (s[3]='b'), left=1. Add 'b', remove s[1]='i'. Window = s[2..3] = "db".

When right=4 (s[4]='a'), left=2. Add 'a', remove s[2]='d'. Window = s[3..4] = "ba". wCount[b]=1, wCount[a]=1. Both match p. matches=26 → return true. ✓

The matches trick eliminates O(26) comparison per slide: Instead of comparing two 26-length arrays each time (O(26) per step = O(26n) total), we maintain matches incrementally. Each add/remove affects at most 1 character, changing matches by at most ±1. O(1) per slide.

Part 9: The Monotonic Deque — Sliding Window Maximum

Problem: Find the maximum in every window of size k.
maxSlidingWindow([1,3,-1,-3,5,3,6,7], k=3) → [3,3,5,5,6,7]
LeetCode 239. Hard. Most important advanced sliding window problem.

The question: How do we know the max of a window in O(1) after each slide?

A max-heap would give O(log n) per slide (need to insert and possibly extract). Can we do O(1)?

The monotonic deque: A deque (double-ended queue) that maintains indices of potential window maximums in decreasing order of their values. The front is always the index of the current maximum.

Invariants:

The deque contains only indices within the current window [left, right].
Values at those indices are in decreasing order from front to back.
The front of the deque is always the index of the window's maximum.

Operations:

When adding nums[right]: pop from the back all indices whose values are ≤ nums[right] (they can never be the maximum while nums[right] is in the window). Add right to back.
When the front index is outside the window (deque[0] < left): pop from front.
The front is always the current maximum.

javascript

function maxSlidingWindow(nums, k) {
  const result = [];
  const deque = [];  // stores indices

  for (let right = 0; right < nums.length; right++) {
    // Remove indices outside the window from front
    if (deque.length > 0 && deque[0] < right - k + 1) {
      deque.shift();
    }

    // Remove indices from back whose values are <= nums[right]
    while (deque.length > 0 && nums[deque[deque.length - 1]] <= nums[right]) {
      deque.pop();
    }

    deque.push(right);

    // Start recording once first full window is formed
    if (right >= k - 1) {
      result.push(nums[deque[0]]);
    }
  }

  return result;
}

Full Dry Run: `maxSlidingWindow([1,3,-1,-3,5,3,6,7], k=3)`

code

deque=[], result=[].

right=0, nums[0]=1:
  Deque empty, skip front check.
  Deque empty, skip back pop.
  Push 0. deque=[0].
  right=0 < k-1=2. No result yet.

right=1, nums[1]=3:
  Front=0. 0 >= 1-3+1=-1. Keep.
  Back: nums[0]=1 <= 3. Pop 0. deque=[].
  Push 1. deque=[1].
  right=1 < 2. No result.

right=2, nums[2]=-1:
  Front=1. 1 >= 2-3+1=0. Keep.
  Back: nums[1]=3 > -1. Keep. (don't pop)
  Push 2. deque=[1,2].
  right=2 >= k-1=2. result.push(nums[1])=3. result=[3]. ✓ Window [0,2]=[1,3,-1], max=3.

right=3, nums[3]=-3:
  Front=1. 1 >= 3-3+1=1. Keep.
  Back: nums[2]=-1 > -3. Keep.
  Push 3. deque=[1,2,3].
  result.push(nums[1])=3. result=[3,3]. ✓ Window [1,3]=[3,-1,-3], max=3.

right=4, nums[4]=5:
  Front=1. 1 >= 4-3+1=2? 1 < 2 → remove front. deque=[2,3].
  Front=2. 2 >= 2. Keep.
  Back: nums[3]=-3 <= 5. Pop 3. deque=[2].
  Back: nums[2]=-1 <= 5. Pop 2. deque=[].
  Push 4. deque=[4].
  result.push(nums[4])=5. result=[3,3,5]. ✓ Window [2,4]=[-1,-3,5], max=5.

right=5, nums[5]=3:
  Front=4. 4 >= 5-3+1=3. Keep.
  Back: nums[4]=5 > 3. Keep.
  Push 5. deque=[4,5].
  result.push(nums[4])=5. result=[3,3,5,5]. ✓ Window [3,5]=[-3,5,3], max=5.

right=6, nums[6]=6:
  Front=4. 4 >= 6-3+1=4. Keep.
  Back: nums[5]=3 <= 6. Pop 5. deque=[4].
  Back: nums[4]=5 <= 6. Pop 4. deque=[].
  Push 6. deque=[6].
  result.push(nums[6])=6. result=[3,3,5,5,6]. ✓ Window [4,6]=[5,3,6], max=6.

right=7, nums[7]=7:
  Front=6. 6 >= 7-3+1=5. Keep.
  Back: nums[6]=6 <= 7. Pop 6. deque=[].
  Push 7. deque=[7].
  result.push(nums[7])=7. result=[3,3,5,5,6,7]. ✓ Window [5,7]=[3,6,7], max=7.

return [3,3,5,5,6,7]. ✓

Complexity: O(n) time — each element is added to and removed from the deque at most once. O(k) space for the deque.

Why the deque is monotonically decreasing: When we encounter a large value, all smaller previous values are useless — they'll never be the maximum as long as the larger value is in the window, and the larger value will outlast them (it arrived later, so it leaves the window later). Removing them from the back maintains the decreasing invariant and doesn't lose any information.

Part 10: Mental Model — When to Reach for Sliding Window

Strong signals:

"Subarray / substring" + some property. The key word is contiguous. Any problem asking about a contiguous range is a sliding window candidate.
"Maximum / minimum / longest / shortest" window satisfying a condition. Variable window: expand to satisfy, shrink to optimize.
"Does any window of size k satisfy..." Fixed window: slide and check.
"Without repeating" / "with at most k distinct" / "containing all of..." These are window constraint formulas.
You have an O(n²) brute force with nested loops where the outer loop picks a start and the inner loop expands. If "start earlier + end later" monotonically changes your property, you can slide.

NOT sliding window when:

The subarray doesn't need to be contiguous — dynamic programming territory.
Moving the window right doesn't monotonically change the property — no valid sliding direction.
You need all pairs, not just adjacent pairs — two-pointer or HashMap.

The expand/contract decision:

Condition not met → expand right.
Condition met but want to optimize (minimize/maximize window size) → shrink left.

Part 11: Real Systems

TCP Sliding Window (Flow Control):
TCP's congestion control uses a literal sliding window. The sender maintains a window of packets that can be "in flight" (sent but not yet acknowledged). The window slides forward as acknowledgments arrive. Window size increases on successful delivery (slow start, congestion avoidance), shrinks on packet loss. This is variable-window sliding window — the constraint is network capacity, the optimization is throughput.

Rate Limiting (Redis + Sliding Window):
The sliding window rate limiter: for each incoming request, count how many requests occurred in the past N seconds. If above threshold, reject. Naive fixed-window (count per minute) has burst problems at window boundaries. Sliding window (rolling count) is more accurate. Redis implements this with sorted sets: timestamp as score, ZRANGEBYSCORE now-window now gives the count. The window slides with real time. Cloudflare and Stripe use this pattern.

Time-Series Aggregation:
Monitoring systems (Prometheus, Datadog) compute rolling averages and moving sums over time-series data. CPU usage: "average over last 5 minutes" is a sliding window of size 300 seconds. As new data points arrive, old ones expire. The fixed-window template (add new, subtract old) computes the rolling average in O(1) per data point.

Kafka Consumer Lag:
Kafka tracks "consumer lag" — how far behind the consumer is from the latest message. The processing pipeline is a sliding window over a stream of events: a window of messages in-flight between produced and consumed. When lag exceeds a threshold, alerting fires. This is the variable-window pattern: expand when messages arrive, contract when they're processed.

Browser Rendering — Paint Buffer:
Browsers batch DOM changes to avoid redundant repaints. The "paint window" collects mutations over a ~16ms frame (60fps). At each frame boundary, the window is committed. New mutations start the next window. This is a fixed-window approach applied to time rather than array position.

Part 12: Vocabulary Map

Term	Definition
Window	Contiguous range [left, right] in an array or string
Window state	Property computed over elements in [left, right]: sum, set, frequency map
Expand	Add arr[right] to state, advance right
Contract / Shrink	Remove arr[left] from state, advance left
Fixed-size window	Window size is always k; slide by adding right and removing left
Variable-size window	Window grows until constraint violated, shrinks until valid
Monotonic deque	Deque maintaining indices in order of their values (for range max/min in O(1))
`have` / `need`	Tracking how many of the required conditions are currently satisfied
Sliding window maximum	The maximum element in each window of size k, computed in O(n) total
TCP sliding window	Network protocol's in-flight packet buffer that adjusts to available bandwidth
Rolling average	Average of a fixed-size window that slides through a time series

Part 13: 5 Practice Problems

1. Trace and Predict

javascript

function f(s, k) {
  let left = 0, max = 0, count = 0;
  const freq = {};
  for (let right = 0; right < s.length; right++) {
    freq[s[right]] = (freq[s[right]] ?? 0) + 1;
    count = Math.max(count, freq[s[right]]);
    while ((right - left + 1) - count > k) {
      freq[s[left]]--;
      left++;
    }
    max = Math.max(max, right - left + 1);
  }
  return max;
}

What does count represent? What does (right - left + 1) - count represent? Trace f("AABABBA", 1). What does this function compute? (LeetCode 424 — know the name.)

2. Find the Waste

Brute force for "find the number of subarrays with product less than k":

code

for i: for j>=i: compute product(i..j), check if < k.

O(n²). The product can increase or decrease as j advances. Is a sliding window applicable here? If yes, what is the invariant? If no, why? (Hint: what happens when a 0 or 1 is in the array?)

3. Failure Analysis

javascript

function longestSubarrayWithSum(nums, k) {
  let left = 0, sum = 0, max = 0;
  for (let right = 0; right < nums.length; right++) {
    sum += nums[right];
    if (sum > k) {
      sum -= nums[left];
      left++;
    }
    max = Math.max(max, right - left + 1);
  }
  return max;
}

This works for arrays with positive integers only. Why does it fail for arrays containing negative integers? Provide a counterexample (an array with negatives where the function returns the wrong answer). What data structure is needed to solve the general case?

4. Design Under Constraints

Design a function maxConsecutiveOnesIII(nums, k): given a binary array and integer k, find the maximum number of consecutive 1s if you can flip at most k 0s.
Example: maxConsecutiveOnesIII([1,1,1,0,0,0,1,1,1,1,0], k=2) → 6.

What is the window constraint? When does the window become invalid? Write the solution and trace the first 6 steps.

5. Reach Beyond

The sliding window maximum used a deque. Now implement the sliding window minimum for window size k. Then implement maxMinRatio(nums, k): for each window of size k, compute max(window) / min(window), return the maximum such ratio across all windows.

Two deques, one for max, one for min. What is the time complexity? When would the max/min ratio in a window be maximized?

Connect Forward

Chapter 7 — Stack & Queue introduces the deque you used in the sliding window maximum. Understanding that the deque's monotonic invariant gives O(1) range queries is the key — the same pattern appears in the "Next Greater Element" problem (Chapter 7a) via a monotonic stack.

The bridge: a monotonic stack/deque is a data structure that answers range queries in O(1) amortized time by discarding elements that can never be the answer. Sliding window maximum is range-max. Next Greater Element is the forward-maximum. They are the same invariant applied in different directions.

Connect Backward

Sliding window inherits the two-pointer framework from Chapter 5. The left and right pointers behave identically — both move only forward, total moves ≤ 2n, giving O(n). The difference: in opposite-ends two pointers, right moves leftward toward left. In sliding window, both left and right move rightward, with left always ≤ right.

The Minimum Window Substring (Part 6) used a HashMap — the frequency counting technique from Chapter 3. Sliding window and HashMap problems overlap heavily because "does this window contain the right mix of characters?" is a frequency question.

Chapter 6 — Sliding Window

Part 1: The Problem That Breaks Brute Force

Part 2: What Sliding Window Is

Part 3: Fixed-Size Window — The Template

Part 4: Variable-Size Window — The Expand/Contract Template

Part 5: Variable-Size Window — Longest Substring Without Repeating Characters

Part 6: Variable-Size Window — Minimum Window Substring

Part 7: Variable-Size Window — Minimum Size Subarray Sum

Part 8: Fixed Window With HashMap — Permutation in String

Part 9: The Monotonic Deque — Sliding Window Maximum

Full Dry Run: maxSlidingWindow([1,3,-1,-3,5,3,6,7], k=3)

Part 10: Mental Model — When to Reach for Sliding Window

Part 11: Real Systems

Part 12: Vocabulary Map

Part 13: 5 Practice Problems

Connect Forward

Connect Backward

Full Dry Run: `maxSlidingWindow([1,3,-1,-3,5,3,6,7], k=3)`