Sliding Window

Constant (Fixed Size) Window

The constant sliding window uses a window of exactly size k.

Core Rule

Expand r every iteration. Once the window hits size k, compute the answer, then shrink from the left to keep the window ready for the next step.

l, r = 0, 0
ans = 0
 
while r < n:
    # Expand: add nums[r] to the window state
 
    if r - l + 1 == k:
        # Window is exactly size k — compute answer
        ans = best(ans, compute_answer_from_window())
        # Shrink: remove nums[l] from the window state
        l += 1
 
return ans

Common Patterns

Problem	Invariant	Window tracks
Maximum Sum Subarray of Size K	window size == k	Running sum
Maximum Average Subarray I	window size == k	Running sum / k
Find All Anagrams in a String	all chars in window unique (or frequency matches)	Character frequency map
Sliding Window Maximum	deque in decreasing order; front is max	Monotonic deque of max candidates
Permutation in String	frequency map satisfies condition	Character frequency map
Min/Max in K-sized Subarrays	deque in monotonic order; front is min/max	Monotonic deque
Longest Substring Without Repeating Characters	all characters in window are unique	Character frequency map
Max Consecutive Ones III	zeros in window ≤ k	Zero count
Longest Repeating Character Replacement	(window size) - (max freq char) ≤ k	Character frequency map

---

Variable Window

The variable sliding window uses two pointers l and r to define a window [l, r]. The core idea is:

Invariant Rule

Before computing the answer, shrink the window from the left until the invariant is satisfied. Only then update the answer.

ans = 0
l = 0
 
for r in range(n):
    # Expand: add nums[r] to the window state
 
    while invariant_is_violated():
        # Shrink: remove nums[l] from the window state
        l += 1
 
    # Invariant is now satisfied for window [l, r]
    ans = best(ans, r - l + 1)
 
return ans

• r moves forward every iteration → every element is added exactly once
• l only moves forward (never backward) → every element is removed at most once
• Time complexity: $O(n)$ — each element is touched at most twice (once by r, once by l)

The Invariant

The invariant depends on the problem. Common examples:

Problem	Invariant (what must hold for [l, r])
Longest Substring Without Repeating Characters	All characters in window are unique
Max Consecutive Ones III	Number of zeros in window $\le k$
Longest Repeating Character Replacement	$(\text{window size})-(\text{max freq char})\le k$
Minimum Size Subarray Sum	(inverted — shrink while valid, not while invalid)

Tip

For “find the longest” problems → shrink while the window is invalid, then update answer. For “find the shortest” problems → shrink while the window is valid, updating answer inside the loop.

Shortest Window Variant

When looking for the minimum length window that satisfies a condition:

ans = float('inf')
l = 0
 
for r in range(n):
    # Expand: add nums[r] to the window state
 
    while invariant_is_satisfied():
        ans = best(ans, r - l + 1)
        # Shrink: remove nums[l] from the window state
        l += 1
 
return ans

Tracking Max/Min in a Window

Use a monotonic deque to track the max or min in a sliding window in $O(n)$ time instead of $O(n\cdot k)$.

Invariant

For max: deque values are monotonically decreasing — front is the max. For min: deque values are monotonically increasing — front is the min.

dq = deque()  # stores indices in monotonic order of values
l = 0
 
for r in range(n):
    # Expand: maintain monotonic invariant (example: decreasing for max)
    while dq and nums[dq[-1]] <= nums[r]:
        dq.pop()
    dq.append(r)
 
    while invariant_is_violated():
        # Shrink: remove from deque if l moves past the front
        if dq[0] == l:
            dq.popleft()
        l += 1
 
    # dq[0] is the index of the max/min in window [l, r]
    ans = best(ans, nums[dq[0]])

Each index is added once and removed at most once → $O(n)$. For min, flip the comparison: remove elements larger than nums[r] from the back.

---

Constant vs Variable

	Constant	Variable
Window size	Fixed at k	Grows and shrinks
Left pointer movement	Advances every step	Advances only to restore invariant
When to use	Problem gives you the window size	Problem asks you to find the optimal window size

Summary

The entire technique boils down to one discipline: maintain the invariant on [l, r] before you compute the answer. Everything else — the data structures, the counters, the conditions — is just bookkeeping for that invariant.