2.3 Sliding Window

Deep Dive: How the Window Actually Slides

Beginner tip: Imagine looking through a magnifying glass that you slide across a sentence. You only see a few characters at a time. As you move right, you add a new character on the right and lose one on the left. The window never goes backward -- that is why it is O(n). Use this pattern whenever you need to find the "best contiguous subarray/substring."

Fixed-Size Window -- Maximum Sum of K Elements

nums = [2, 1, 5, 1, 3, 2], k = 3:

[2, 1, 5] 1  3  2   sum=8
 2 [1, 5, 1] 3  2   sum=8-2+1=7   (remove left, add right)
 2  1 [5, 1, 3] 2   sum=7-1+3=9   <-- MAX
 2  1  5 [1, 3, 2]  sum=9-5+2=6

Why it is O(n) not O(n*k): Instead of re-summing k elements each time, you subtract the element leaving the window and add the one entering. One addition, one subtraction per step.

Variable-Size Window -- Longest Without Repeating

s = "abcabcbb":

Step   Window     Action                  Seen        Best
 1     [a]        add 'a'                 {a:0}        1
 2     [a,b]      add 'b'                 {a:0,b:1}    2
 3     [a,b,c]    add 'c'                 {a:0,b:1,c:2} 3
 4     [b,c,a]    'a' dup! move left->1   {a:3,b:1,c:2} 3
 5     [c,a,b]    'b' dup! move left->2   {a:3,b:4,c:2} 3
 6     [a,b,c]    'c' dup! move left->3   {a:3,b:4,c:5} 3
 7     [c,b]      'b' dup! move left->5   {a:3,b:6,c:5} 2
 8     [b]        'b' dup! move left->7   {a:3,b:7,c:5} 1

The variable window contract: Expand right always. Shrink left ONLY when the window becomes invalid. The window represents the current best candidate.

The Mental Model

RIGHT pointer: explores new territory (expands window)
LEFT pointer:  cleans up when constraint is violated (shrinks window)

They both move ONLY forward -> each element visited at most twice -> O(n)

---

Quick Reference (Cheat Sheet)

Before You Start -- How to Think About Sliding Window

Why It Works

Brute force: Check all subarrays = O(n^2). Sliding window: Reuse the previous window's computation = O(n).

The Core Insight

Instead of recomputing from scratch for each subarray, SLIDE the window: add the new element on the right, remove the old element on the left.

Two Types

FIXED SIZE (window = K):
  Window is always size K. Slide right, update answer.
  Signal: "maximum sum of subarray of size K", "average of K elements"

VARIABLE SIZE (shrink/expand):
  Expand right to include more. Shrink left when constraint violated.
  Signal: "longest/shortest subarray with condition", "minimum window containing X"

Fixed Window Template

for r in range(n):
    window.add(arr[r])        # expand right
    if r >= k:
        window.remove(arr[r-k])  # remove leftmost
    if r >= k - 1:
        update_answer()        # window is full size

Variable Window Template

l = 0
for r in range(n):
    window.add(arr[r])        # expand right
    while window_invalid():    # shrink left until valid
        window.remove(arr[l])
        l += 1
    update_answer()            # current window is valid

When You See a Problem, Ask Yourself

1. "Subarray/substring of size K"? -> Fixed sliding window
2. "Longest/shortest subarray with condition"? -> Variable sliding window
3. "At most K distinct elements"? -> Variable window + HashMap for counts
4. "Permutation/anagram in string"? -> Fixed window + frequency comparison
5. "Maximum in each window"? -> Sliding window + monotonic deque

Common Mistakes

• Variable window: shrinking with if instead of while (may need to shrink multiple times)
• Not updating the answer at the right time (after adding? after shrinking?)
• For frequency-based windows: decrementing count to 0 vs removing key entirely

Problems

#	Problem	Type	Status
1	Maximum Sum Subarray of Size K	Fixed	[ ]
2	Longest Substring Without Repeating Characters	Variable	[ ]
3	Minimum Window Substring	Variable	[ ]
4	Longest Repeating Character Replacement	Variable	[ ]
5	Permutation in String	Fixed + Freq	[ ]
6	Sliding Window Maximum	Deque	[ ]
7	Fruit Into Baskets	Variable	[ ]
8	Minimum Size Subarray Sum	Variable	[ ]
9	Find All Anagrams in a String	Fixed + Freq	[ ]

Notes