Chapter 6a — Sliding Window Problem Patterns

Each problem here teaches one new decision: what to track in the window, when to expand, when to shrink.

Pattern Map

Problem 1: Maximum Average Subarray I

Problem: Find the contiguous subarray of length k with the maximum average.
findMaxAverage([1,12,-5,-6,50,3], k=4) → 12.75 (subarray [12,-5,-6,50])
LeetCode 643.

Four Questions

Q1: What do I have? Array of integers, window size k.
Q2: What do I want? Maximum average over any window of length exactly k.
Q3: What is the brute force? For every starting position, sum k elements and divide. O(nk).
Q4: Where is the waste? Recomputing overlapping sums. Fixed-window slide: O(n).

function findMaxAverage(nums, k) {
  let sum = 0;
  for (let i = 0; i < k; i++) sum += nums[i];

  let maxSum = sum;

  for (let i = k; i < nums.length; i++) {
    sum += nums[i] - nums[i - k];  // add right, remove left
    maxSum = Math.max(maxSum, sum);
  }

  return maxSum / k;
}

Dry run: findMaxAverage([1,12,-5,-6,50,3], k=4)

Init: sum = 1+12-5-6 = 2. maxSum=2.
i=4: sum = 2 + 50 - 1 = 51. maxSum=51.
i=5: sum = 51 + 3 - 12 = 42. maxSum=51.
return 51/4 = 12.75. ✓

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

Interview signal: Anytime you see "average of k consecutive elements," think fixed window. Averaging is just summing divided by k — same sliding mechanics.

Problem 2: Longest Substring With At Most K Distinct Characters

Problem: Find the length of the longest substring with at most k distinct characters.
lengthOfLongestSubstringKDistinct("eceba", k=2) → 3 ("ece")
LeetCode 340.

Four Questions

Q1: What do I have? A string, integer k.
Q2: What do I want? Longest substring using at most k different characters.
Q3: What is the brute force? All O(n²) substrings, count distinct per substring. O(n³).
Q4: Where is the waste? When we add a character and distinct count exceeds k, we don't need to restart — just shrink from left until we're back to k distinct.

State: HashMap tracking character → frequency in current window. Distinct count = map.size.
Constraint: map.size <= k.
Shrink when: map.size > k.

function lengthOfLongestSubstringKDistinct(s, k) {
  const freq = new Map();
  let left = 0, max = 0;

  for (let right = 0; right < s.length; right++) {
    // Expand: add s[right]
    freq.set(s[right], (freq.get(s[right]) ?? 0) + 1);

    // Shrink: while more than k distinct
    while (freq.size > k) {
      const leftChar = s[left];
      freq.set(leftChar, freq.get(leftChar) - 1);
      if (freq.get(leftChar) === 0) freq.delete(leftChar);
      left++;
    }

    max = Math.max(max, right - left + 1);
  }

  return max;
}

Dry run: lengthOfLongestSubstringKDistinct("eceba", k=2)

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

right=0 'e': freq={e:1}. size=1<=2. max=1.
right=1 'c': freq={e:1,c:1}. size=2<=2. max=2.
right=2 'e': freq={e:2,c:1}. size=2<=2. max=3.
right=3 'b': freq={e:2,c:1,b:1}. size=3>2. Shrink:
  remove s[0]='e': freq={e:1,c:1,b:1}. left=1. size=3>2.
  remove s[1]='c': freq={e:1,b:1}. delete 'c'. left=2. size=2. Stop.
  max=max(3, 3-2+1)=max(3,2)=3.
right=4 'a': freq={e:1,b:1,a:1}. size=3>2. Shrink:
  remove s[2]='e': freq={b:1,a:1}. delete 'e'. left=3. size=2. Stop.
  max=max(3, 4-3+1)=max(3,2)=3.

return 3. ✓ ("ece" at indices 0-2)

Complexity: O(n) time, O(k) space (map holds at most k+1 characters at any time before shrinking).

Connection to Problem 5 (Chapter 5): k=1 gives longest substring with 1 distinct character. k=∞ (or k=26) gives the full string. The "without repeating characters" problem is k=1 with the constraint "each character appears at most once" — equivalent when all characters are distinct.

Problem 3: Fruits Into Baskets

Problem: You have two baskets. Each basket holds one type of fruit. Pick the maximum number of fruits from a contiguous section of trees, each holding exactly one type of fruit, using only your two baskets.
totalFruit([1,2,1,2,3]) → 4 (pick [1,2,1,2])
LeetCode 904.

Translation: Longest subarray with at most 2 distinct values. Literally the same as Problem 2 with k=2.

function totalFruit(fruits) {
  return lengthOfLongestSubstringKDistinct(fruits.map(String).join(''), 2);
  // Or directly:
  const freq = new Map();
  let left = 0, max = 0;
  for (let right = 0; right < fruits.length; right++) {
    freq.set(fruits[right], (freq.get(fruits[right]) ?? 0) + 1);
    while (freq.size > 2) {
      const lf = fruits[left];
      freq.set(lf, freq.get(lf) - 1);
      if (freq.get(lf) === 0) freq.delete(lf);
      left++;
    }
    max = Math.max(max, right - left + 1);
  }
  return max;
}

Dry run: totalFruit([1,2,1,2,3])

right=0(1): freq={1:1}. max=1.
right=1(2): freq={1:1,2:1}. max=2.
right=2(1): freq={1:2,2:1}. max=3.
right=3(2): freq={1:2,2:2}. max=4.
right=4(3): freq={1:2,2:2,3:1}. size=3>2. Shrink:
  remove fruits[0]=1: freq={1:1,2:2,3:1}. left=1. size=3.
  remove fruits[1]=2: freq={1:1,2:1,3:1}. left=2. size=3.
  remove fruits[2]=1: freq={2:1,3:1}. delete 1. left=3. size=2. Stop.
  max=max(4, 4-3+1)=max(4,2)=4.

return 4. ✓

Interview insight: Many "at most k types" problems in interviews are disguised as real-world scenarios (baskets, colors, categories). Recognize the abstraction and apply the pattern.

Problem 4: Longest Repeating Character Replacement

Problem: Given a string and integer k, find the longest substring where you can replace at most k characters to make all characters the same.
characterReplacement("AABABBA", k=1) → 4
LeetCode 424. Classic. Google, Meta.

Four Questions

Q1: What do I have? A string of uppercase letters, replacement budget k.
Q2: What do I want? Longest window where (window length - most frequent character count) ≤ k. Because if the most frequent character appears maxFreq times, we need to change windowLen - maxFreq characters, which must be ≤ k.
Q3: What is the brute force? All O(n²) windows, find max frequency per window. O(n³).
Q4: Where is the waste? We can maintain the window's max frequency incrementally. When the "replacements needed" exceeds k, shrink.

function characterReplacement(s, k) {
  const freq = new Array(26).fill(0);
  const A = 'A'.charCodeAt(0);
  let left = 0, maxFreq = 0, max = 0;

  for (let right = 0; right < s.length; right++) {
    freq[s.charCodeAt(right) - A]++;
    maxFreq = Math.max(maxFreq, freq[s.charCodeAt(right) - A]);

    // If replacements needed exceed k, shrink
    while ((right - left + 1) - maxFreq > k) {
      freq[s.charCodeAt(left) - A]--;
      left++;
      // Note: we don't update maxFreq here (see explanation below)
    }

    max = Math.max(max, right - left + 1);
  }

  return max;
}

Dry run: characterReplacement("AABABBA", k=1)

freq=[0..0], left=0, maxFreq=0, max=0. A=0, B=1.

right=0 'A': freq[0]=1. maxFreq=1. windowLen=1. 1-1=0<=1. max=1.
right=1 'A': freq[0]=2. maxFreq=2. windowLen=2. 2-2=0<=1. max=2.
right=2 'B': freq[1]=1. maxFreq=2. windowLen=3. 3-2=1<=1. max=3.
right=3 'A': freq[0]=3. maxFreq=3. windowLen=4. 4-3=1<=1. max=4.
right=4 'B': freq[1]=2. maxFreq=3. windowLen=5. 5-3=2>1. Shrink:
  remove s[0]='A': freq[0]=2. left=1.
  windowLen=4. 4-3=1<=1. Stop.
  max=max(4,4)=4.
right=5 'B': freq[1]=3. maxFreq=3. windowLen=5. 5-3=2>1. Shrink:
  remove s[1]='A': freq[0]=1. left=2.
  windowLen=4. 4-3=1<=1. Stop.
  max=4.
right=6 'A': freq[0]=2. maxFreq=3. windowLen=5. 5-3=2>1. Shrink:
  remove s[2]='B': freq[1]=2. left=3.
  windowLen=4. 4-3=1<=1. Stop.
  max=4.

return 4. ✓

The maxFreq subtlety: When we shrink, we don't update maxFreq. This is intentional. We only need the answer to grow — if the current window can't beat the best we've found (which used a window with maxFreq most-frequent chars), we don't need to shrink further. maxFreq only increases, so the window never shrinks smaller than the best answer we've found. This is a subtle optimization that makes the while loop behave like an if (shrink by exactly 1 when needed), keeping the amortized cost O(1) per step rather than O(n).

Complexity: O(n) time, O(1) space (26-char array).

Problem 5: Minimum Window Substring

Problem: Find the minimum window in s containing all characters of t.
minWindow("ADOBECODEBANC", "ABC") → "BANC"
LeetCode 76. Fully developed in Chapter 6. Restated here with key pattern notes.

function minWindow(s, t) {
  const need = new Map();
  for (const c of t) need.set(c, (need.get(c) ?? 0) + 1);

  const window = new Map();
  let have = 0, needCount = need.size;
  let left = 0, minLen = Infinity, result = "";

  for (let right = 0; right < s.length; right++) {
    const c = s[right];
    window.set(c, (window.get(c) ?? 0) + 1);
    if (need.has(c) && window.get(c) === need.get(c)) have++;

    while (have === needCount) {
      if (right - left + 1 < minLen) {
        minLen = right - left + 1;
        result = s.slice(left, right + 1);
      }
      const lc = s[left];
      window.set(lc, window.get(lc) - 1);
      if (need.has(lc) && window.get(lc) < need.get(lc)) have--;
      left++;
    }
  }

  return result;
}

Pattern note: This is a "shortest window satisfying constraint" problem. The constraint is "window contains all of t." The trick is tracking have/need (satisfied character types) rather than comparing full maps on every step.

Complexity: O(|s| + |t|) time, O(|t|) space.

Problem 6: Subarray Product Less Than K

Problem: Count subarrays where the product of all elements is less than k.
numSubarrayProductLessThanK([10,5,2,6], k=100) → 8
LeetCode 713.

Four Questions

Q1: What do I have? Array of positive integers, threshold k.
Q2: What do I want? Count of contiguous subarrays with product < k.
Q3: What is the brute force? All O(n²) subarrays, compute product each. O(n²) or O(n³).
Q4: Where is the waste? When the right pointer is at index right and the current window [left, right] has product < k, then every subarray ending at right and starting anywhere from left to right also has product < k. Count: right - left + 1 such subarrays.

function numSubarrayProductLessThanK(nums, k) {
  if (k <= 1) return 0;  // no positive product can be < 1

  let left = 0, product = 1, count = 0;

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

    while (product >= k) {
      product /= nums[left];
      left++;
    }

    // All subarrays ending at right and starting from left..right are valid
    count += right - left + 1;
  }

  return count;
}

Dry run: numSubarrayProductLessThanK([10,5,2,6], k=100)

left=0, product=1, count=0.

right=0(10): product=10. 10<100. count += 0-0+1 = 1. count=1.
  (subarrays: [10])

right=1(5): product=50. 50<100. count += 1-0+1 = 2. count=3.
  (new subarrays: [5], [10,5])

right=2(2): product=100. 100>=100. 
  product/=nums[0]=10 → product=10. left=1.
  10<100. count += 2-1+1 = 2. count=5.
  (new subarrays: [2], [5,2])

right=3(6): product=60. 60<100. count += 3-1+1 = 3. count=8.
  (new subarrays: [6], [2,6], [5,2,6])

return 8. ✓

Why count += right - left + 1: When window is [left, right], the valid subarrays ending at right are: [right], [right-1, right], ..., [left, right]. That's right - left + 1 subarrays. All have products ≤ the window product (since all nums are positive, subsets have smaller or equal products). Counting them all at once is the key to O(n) total count.

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

Problem 7: Find All Anagrams in a String

Problem: Given strings s and p, find all start indices of p's anagrams in s.
findAnagrams("cbaebabacd", "abc") → [0, 6]
LeetCode 438. (Previewed at end of Chapter 3a — now with full sliding window treatment.)

The Pattern

Anagram = same character frequencies. Fixed window of size p.length. At each position, check if window frequencies match p's frequencies. Use the matches counter technique from Chapter 6.

function findAnagrams(s, p) {
  if (p.length > s.length) return [];

  const pFreq = new Array(26).fill(0);
  const wFreq = new Array(26).fill(0);
  const A = 'a'.charCodeAt(0);
  const result = [];

  for (const c of p) pFreq[c.charCodeAt(0) - A]++;

  // matches: how many of 26 chars have equal freq in window and p
  let matches = 0;

  // Initialize first window
  for (let i = 0; i < p.length; i++) {
    wFreq[s.charCodeAt(i) - A]++;
  }
  for (let i = 0; i < 26; i++) {
    if (wFreq[i] === pFreq[i]) matches++;
  }

  if (matches === 26) result.push(0);

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

    // Add right character
    const ri = s.charCodeAt(right) - A;
    if (wFreq[ri] === pFreq[ri]) matches--;          // was matching
    wFreq[ri]++;
    if (wFreq[ri] === pFreq[ri]) matches++;          // now matching

    // Remove left character
    const li = s.charCodeAt(left) - A;
    if (wFreq[li] === pFreq[li]) matches--;          // was matching
    wFreq[li]--;
    if (wFreq[li] === pFreq[li]) matches++;          // now matching

    if (matches === 26) result.push(left + 1);      // window starts at left+1
  }

  return result;
}

Dry run: findAnagrams("cbaebabacd", "abc")

p="abc". pFreq: a=1, b=1, c=1. All others 0.

First window "cba" (indices 0-2): wFreq: a=1, b=1, c=1.
matches: a:1=1✓, b:1=1✓, c:1=1✓, all others 0=0✓. matches=26. result=[0].

right=3 'd', left=0 'c':
  Add 'd': wFreq[d]=0→1. pFreq[d]=0. was matching (0=0), now not (1≠0). matches=25. wFreq[d]=1. still 1≠0. matches stays 25.
  Remove 'c': wFreq[c]=1=pFreq[c]=1 → was matching: matches=24. wFreq[c]=0. 0≠1. not matching. matches=24.
  24≠26. No anagram.

right=4 'e', left=1 'b':
  Add 'e': was 0=0(match), matches=23. wFreq[e]=1. 1≠0. still 23.
  Remove 'b': wFreq[b]=1=pFreq[b]=1 → matches=22. wFreq[b]=0. 0≠1. 22.
  22≠26.

right=5 'a', left=2 'a':
  Add 'a': wFreq[a]=1=pFreq[a]=1 → was matching, matches=21. wFreq[a]=2. 2≠1. 21.
  Remove 'a': wFreq[a]=2≠pFreq[a]=1 → not matching, stays 21. wFreq[a]=1. 1=1 → now matching, matches=22.
  22≠26.

right=6 'b', left=3 'd':
  Add 'b': wFreq[b]=0=pFreq[b]... wait, let me recheck state.

Let me track the state more carefully through each step by tracking wFreq explicitly:

After first window "cba": wFreq={a:1,b:1,c:1,d:0,e:0,...}. matches=26.

After right=3 'd', remove 'c': wFreq={a:1,b:1,c:0,d:1,e:0,...}. matches=24 (c and d don't match). After right=4 'e', remove 'b': wFreq={a:1,b:0,c:0,d:1,e:1,...}. matches=22 (b,c,d,e don't match, but b and c need 1 and 1, we have 0 and 0 — actually c: need=1, have=0: no match; e: need=0, have=1: no match).

Actually let me just count properly. After each step, matches = number of chars where wFreq[i] === pFreq[i].

After sliding through to right=6 'b', window is s[4..6] = "eba". wFreq={a:1,b:1,e:1}. pFreq={a:1,b:1,c:1}. a: 1=1✓, b: 1=1✓, c: 0≠1✗, e: 1≠0✗. matches=24. Not 26.

After right=7 'a', left=4 'e', window is s[5..7]="bab": wFreq={a:2,b:1}. No anagram.

After right=8 'c', left=5 'a', window is s[6..8]="abc" (well, s[6]='b',s[7]='a',s[8]='c'="bac"): wFreq={a:1,b:1,c:1}. matches=26! result.push(left+1 = 5+1 = 6). result=[0,6]. ✓

Complexity: O(|s| + |p|) time, O(1) space (26-char arrays).

Problem 8: Sliding Window Maximum

Fully developed in Chapter 6, Part 9. Key pattern points:

• Monotonic deque maintains potential maximums in decreasing order.
• Each element enters and exits the deque exactly once → O(n) total.
• Front of deque = current maximum → O(1) per window.
• Use array as deque with shift() for front removal and pop() for back removal. (For production, use a doubly-linked list deque — shift() on arrays is O(n). But for interviews, array deque with indices is accepted.)

Pattern Recognition Decision Tree

New sliding window problem:

1. Fixed window size k given?
   YES → Fixed window template.
        State depends on problem: sum (arithmetic), freq array (anagram), etc.
        O(n) guaranteed.
   NO → Variable window. Ask:

2. Maximize window or minimize window?
   MAXIMIZE (longest subarray with X):
     → Expand right always.
     → Shrink left when constraint VIOLATED.
     → Record length when constraint satisfied.
   MINIMIZE (shortest window containing X):
     → Expand right always.
     → Shrink left when constraint SATISFIED (found valid window, try to reduce).
     → Record length when constraint satisfied, then shrink once more.

3. What state do I track in the window?
   Sum/product of elements → running number
   Character/value frequencies → HashMap or 26-char array
   Distinct count → HashMap.size
   "Have all required elements" → have/need counter pattern
   Range max/min → monotonic deque

4. O(n) sanity check:
   Each element enters window once, exits once.
   State update per element = O(1) or O(log n).
   Total: O(n) or O(n log n).

5 Practice Problems

1. Trace and Predict

function f(nums) {
  let left = 0, right = 0, zeros = 0, max = 0;
  while (right < nums.length) {
    if (nums[right] === 0) zeros++;
    while (zeros > 1) {
      if (nums[left] === 0) zeros--;
      left++;
    }
    max = Math.max(max, right - left + 1);
    right++;
  }
  return max;
}

Trace f([1,0,1,1,0,1]). What does this function compute? What is the constraint? What is zeros tracking? Generalize: how would you change this to allow at most k zeros?

2. Find the Waste

You want "longest subarray with sum exactly equal to k" (not ≤ k, not ≥ k, exactly k). Can sliding window solve this directly? Why or why not? What happens when the array contains negative integers? (The answer is a prefix sum + HashMap — how do they handle the "exactly" constraint differently from sliding window's "at most" structure?)

3. Failure Analysis

function minWindow(s, t) {
  const need = {};
  for (const c of t) need[c] = (need[c] ?? 0) + 1;
  const have = {};
  let formed = 0, left = 0, min = Infinity, res = "";
  for (let right = 0; right < s.length; right++) {
    have[s[right]] = (have[s[right]] ?? 0) + 1;
    if (need[s[right]] && have[s[right]] === need[s[right]]) formed++;
    if (formed === Object.keys(need).length) {
      if (right - left + 1 < min) { min = right - left + 1; res = s.slice(left, right+1); }
      have[s[left]]--;
      left++;
    }
  }
  return res;
}

The shrink logic has a bug. Identify it. Hint: what should happen if removing s[left] causes a required character to drop below its needed frequency? Write the correct version.

4. Design Under Constraints

Design numberOfSubstrings(s) where s contains only 'a', 'b', 'c'. Count substrings containing at least one of each character.

Constraint: O(n) time.

Hint: "at least one of each" is hard to shrink for directly. Use the complement: total substrings - substrings missing at least one character. Or: for each right endpoint, find the leftmost valid left. All subarrays from that left to 0 are valid — count them.

5. Reach Beyond

shortestSubarrayWithSumAtLeastK(nums, k) where nums can contain negative integers.
Example: nums=[2,-1,2], k=3 → 3 (entire array, sum=3).

Sliding window fails because shrinking left doesn't necessarily decrease the sum (could increase it if we remove a negative). The solution uses a monotonic deque on prefix sums. Research or derive: what property do we need from the prefix sum array, and how does the deque maintain it? This is LeetCode 862 (Hard) — it combines prefix sums, deque, and the sliding window idea into one algorithm.