Sliding Window

Core Concepts

Sliding window — a technique that maintains a contiguous subarray or substring [left, right] over a sequence, with both pointers advancing forward only. Because neither pointer ever retreats, each element is added and removed at most once, giving O(n) total work regardless of window size.

Window validity — the core boolean predicate on the window's current contents. Every sliding window problem reduces to: "what does it mean for a window to be valid, and do I expand or shrink to find valid windows?"

Fixed-size window — window size is held at exactly k throughout; right - left + 1 = k at all times after initialization. The window slides by adding arr[right] and evicting arr[left] simultaneously.

Variable-size window (grow-then-shrink) — expand right to include new elements; shrink from left when the window becomes invalid. Used for longest-valid-subarray problems.

Variable-size window (shrink-while-valid) — expand right, then shrink from left as long as the window stays valid. Used for shortest-valid-subarray problems; record result during the shrink.

Amortized O(n) — the invariant that makes sliding window efficient: over the full traversal, right moves from 0 to n−1 (n increments) and left moves from 0 to at most n−1 (n increments total). Inner loops are amortized, not O(n) per outer step.

---

Structural Invariants

---

Types / Variants

---

Key Algorithms

Fixed Window: Sliding Over k-Length Windows

Compute the aggregate for the first k elements, then slide: subtract the leaving element and add the entering element. O(n) time, O(1) extra space (for sum/count) or O(k) for a deque.

window_sum = sum(arr[:k])
for i in range(k, n):
    window_sum += arr[i] - arr[i - k]

Variable Window: Longest Valid Subarray

Expand right unconditionally. When the window becomes invalid, shrink left until valid. Record right - left + 1 after each expansion (the window is always valid at this point). O(n) amortized.

Insight: You never need to restart from scratch — shrinking from left is always sufficient because the right endpoint never contributes to invalidity from the left side.

Variable Window: Shortest Valid Subarray

Expand right until valid. Then shrink left as long as the window stays valid, recording the window length before each shrink. O(n) amortized.

Insight: Record result inside the shrink loop, not outside — the window is shrunk past validity to find the true minimum length, so you must capture the valid state before losing it.

while left <= right and valid(window):
    res = min(res, right - left + 1)
    remove arr[left] from window; left += 1

Exactly K → At-Most K Transformation

For problems asking "count subarrays with exactly K distinct elements (or exactly K occurrences)": define atmost(k) = count of subarrays with at most k of the target. Then exactly(k) = atmost(k) − atmost(k−1).

Insight: "At most K" has a clean monotonic shrink structure (add element, if count > k shrink left); "exactly K" does not, because removing from left might overshoot. The subtraction eliminates the boundary case.

Sliding Window Maximum (Monotonic Deque)

Maintain a deque of indices in decreasing order of arr[index]. For each new element: pop from the back while arr[back] ≤ arr[right] (it can never be the max while right exists). Pop from the front when deque[0] < left (index left the window). The front is always the current window max. O(n) time, O(k) space.

Insight: Any element smaller than a newer element can never be the window max — it will age out before the newer element does.

dq = collections.deque()
for i in range(n):
    while dq and arr[dq[-1]] <= arr[i]: dq.pop()
    dq.append(i)
    if dq[0] < i - k + 1: dq.popleft()

---

Advanced Techniques

Frequency Map with Valid-Count Variable

Tracking window validity via a full O(26) or O(k) scan each step degrades to O(n·k). Instead, maintain a count variable = number of "satisfied" characters or conditions. Update count as each element enters or exits; O(1) validity check per step.

When to use over naive check: whenever window validity depends on per-element frequency meeting a threshold (anagram detection, minimum window substring). If validity is a single numeric aggregate (sum ≥ target), a simple variable suffices.

Two-Window Difference (Exactly K via Complementary Bounds)

When exactly(k) can't be computed directly, compute it as f(k) − f(k−1) where f is a monotonically solvable variant (at-most-k). Run two sliding window passes simultaneously.

When to use over single-pass: whenever the validity predicate flips from monotone to non-monotone as elements are added (distinct count, exact sum with negatives).

Prefix Sum Preprocessing Before Window

For windows where the aggregate is a subarray sum and the target changes (e.g., "max sum ≤ target"), precompute prefix sums and use a sorted structure or deque on prefix sums. O(n log n).

When to use over pure window: when values can be negative (pure sliding window breaks — removing the left element might decrease the sum, so shrinking never helps) or when the target varies per window. See also: prefix-sum.md.

Shrink-Side Selection: Left vs Right

Standard sliding window always shrinks from the left. When elements have a sorted or ordered structure, shrinking from the right can also be valid (rare — usually this is two pointers). Confirm: is there a monotonic relationship between window size and validity? If yes, one-sided shrink from left works. If not, the problem may require a different technique.

---

Problem Taxonomy

By Problem Category

Problem Signal → Technique

---

Common Patterns

---

Edge Cases & Pitfalls

• Shrinking past left > right: When no element satisfies the constraint alone, the shrink loop can push left past right. Guard with left <= right in the inner while condition or the window size goes negative.

• Recording result outside the shrink (min-length problems): Recording after the outer loop ends misses the minimum — the window is invalid when the loop exits. Record inside the while loop before shrinking.

• Off-by-one in window size: Window size is right - left + 1, not right - left. Getting this wrong produces k-1 sized windows or skips one-element answers.

• Stale deque front in sliding window maximum: After advancing left, the deque front may refer to an index now outside the window. Always check dq[0] < left and popleft before reading the maximum.

• All-negative values with sum ≥ target: If target ≤ 0 and all elements are negative, the answer may be the entire array. Pure grow-shrink works; but if you filter for "sum > 0" as a validity shortcut, you'll miss it.

• Frequency map not decremented on left eviction: Leaving stale positive counts makes the window appear to still contain evicted characters, inflating the valid-count and breaking the invariant.

• Product overflow in product-window problems: Multiplying k integers of value up to 10^4 overflows a 32-bit integer. Use Python (arbitrary precision) or track log-sum instead of product.

• Distinct count not decremented to zero: When an element's frequency drops to 0 on eviction, remove it from the map (or decrement the distinct counter). Leaving it as a zero-count entry over-counts distinct elements.

• Applying grow-shrink to arrays with negative numbers: If values can be negative, removing the leftmost element may decrease the sum, so shrinking never helps restore sum < target. The window technique only works when adding an element monotonically moves the aggregate in one direction.

---

Implementation Notes

• Python's collections.deque supports O(1) popleft and pop; use it for the monotonic deque, not a plain list.
• A 26-length integer array ([0] * 26) with ord(c) - ord('a') indexing is faster than defaultdict(int) for lowercase-only character problems.
• Python collections.Counter subtraction silently drops zero and negative counts — avoid it for incremental frequency tracking inside a window; maintain the map manually.
• For the at-most-K subtraction pattern, write a single atmost(k) helper and call it twice; duplicating the loop body introduces subtle divergence bugs.
• When k = 0 in a fixed window, the answer is trivially 0 or empty — guard before initializing the window sum.
• For sliding window problems on strings, indexing into a bytearray (s.encode()) is faster than indexing into a Python str in tight loops, though rarely needed in interviews.

---

Cross-Topic Relations

---

Interview Reference

Must-Know Problems

Fixed window

• Maximum Sum Subarray of Size K (basic template)
• Maximum Average Subarray I (LC 643)
• Sliding Window Maximum (LC 239) — monotonic deque
• Find All Anagrams in a String (LC 438)
• Permutation in String (LC 567)

Variable window — longest

• Longest Substring Without Repeating Characters (LC 3)
• Longest Substring with At Most K Distinct Characters (LC 340)
• Longest Repeating Character Replacement (LC 424)
• Fruit Into Baskets (LC 904)
• Max Consecutive Ones III (LC 1004)

Variable window — shortest

• Minimum Size Subarray Sum (LC 209)
• Minimum Window Substring (LC 76)
• Minimum Operations to Reduce X to Zero (LC 1658)

Exactly-K transformation

• Subarrays with K Different Integers (LC 992)
• Number of Substrings Containing All Three Characters (LC 1358)
• Count Number of Nice Subarrays (LC 1248)

Hard

• Minimum Window Substring (LC 76)
• Sliding Window Maximum (LC 239)
• Substring with Concatenation of All Words (LC 30)

Additional LeetCode Coverage

• K Radius Subarray Averages (LC 2090)
• Contains Duplicate II (LC 219)

Clarification Questions to Ask

• Are values guaranteed positive, or can they be zero or negative? (Determines if grow-shrink is valid for sum constraints.)
• Is the array or string sorted? (Sorted order sometimes enables two pointers instead of a window.)
• Is the window size k fixed, or must you find the optimal size?
• For "distinct" problems: does "distinct" count values or indices? Are duplicates allowed in the input?
• For string problems: lowercase only, or arbitrary characters? Case-sensitive?
• For count problems: overlapping subarrays count separately?
• Is the input guaranteed non-empty? What is the minimum valid answer if no window satisfies the constraint?

Common Interview Mistakes

• Using a fixed-window approach when the problem requires finding the optimal window size — misreading "find k" as "given k."
• Tracking frequency correctly on expand but forgetting to decrement (not delete) on shrink, so the frequency map grows unboundedly.
• Recording the result after the inner shrink loop rather than inside it for minimum-length problems, always returning a slightly too-large value.
• Forgetting to evict stale indices from the deque front in sliding window maximum problems, returning a max from outside the current window.
• Applying sliding window to sum-equals problems with negative numbers — the monotone property breaks, making the shrink useless.
• Initializing the result to 0 instead of float('inf') for minimum-length problems when no valid window exists.

Typical Follow-Up Escalations

• "Now do it with negative numbers in the array." → Sliding window breaks; pivot to prefix sums + sorted structure or deque on prefix sums (O(n log n)).
• "Now count subarrays with exactly K distinct instead of at most K." → Apply the at-most-K minus at-most-(K−1) transformation.
• "Can you find the maximum of each window in O(n)?" → Introduce the monotonic deque; naive is O(nk).
• "What if k can be up to n?" → Deque still O(n); naive is O(n²) — highlight the asymptotic win.
• "Now do minimum window substring with wildcards in the pattern." → Expand frequency map to handle wildcard matching; same window structure, more complex validity predicate.