# The Sliding Window Pattern > Learn the sliding window technique: solve longest/shortest subarray and substring problems in O(n) with the expand-right, shrink-left template. Canonical: https://ironclad.academy/dsa/techniques/sliding-window | Difficulty: medium | Topics: Sliding Window, Two Pointers, Arrays, Strings, Hash Tables Asked at: Amazon, Google, Meta, Microsoft ## Key takeaways - The tell is "longest/shortest/min/max over a contiguous subarray" — that phrase almost always maps to a sliding window. - Fixed window: add the new right element, drop the element that just left; one pass, O(n). - Variable window: expand right freely, shrink left until the invariant holds again; each element enters and exits at most once. - Pair a hash map or hash set with the window when the constraint involves character counts or element membership. - The classic bug is forgetting to shrink — when the invariant breaks, keep moving left until it is restored, not just once. > **In one line:** Sliding window replaces two nested loops with a single O(n) pass by maintaining a moving range [left, right] and adjusting its boundaries instead of restarting the inner loop from scratch. The pattern shows up any time a problem asks for the best (longest, shortest, max, min) contiguous chunk of an array or string subject to some constraint. Brute force tries every possible start index and scans forward — that is O(n²). Sliding window realizes that when you move the start forward by one, most of the work you just did is still valid and you can reuse it. There are two flavors: **fixed** (the window is always exactly k wide) and **variable** (the window grows and shrinks to satisfy a constraint). Both follow the same rhythm: a `right` pointer that only moves forward, and a `left` pointer that catches up when needed. [Interactive visualizer on the original page: array — why index-based windows are cheap: array access is O(1)] The visualizer shows the property the whole pattern rests on: reading `arr[i]` is O(1), so moving `left` or `right` by one costs a single constant-time read — no scanning, no copying. Internally, the window state is almost always a running sum, a count map ([hash table](/dsa/structures/hash-table)), or a set — something that can be updated in O(1) as the boundaries move. The whole point is that you never re-process an element you already processed. ## The tell: when does this pattern apply? You are staring at a problem. Something about it feels like it wants nested loops. Before you write them, check for three things: 1. The input is a **linear sequence** — an [array](/dsa/structures/arrays) or a string. 2. The answer is about a **contiguous subarray or substring** (not arbitrary subsets). 3. The objective is "longest", "shortest", "minimum", "maximum", "exactly k", or "contains all of X". If all three are true, try sliding window before anything else. The brute force for these problems almost always looks like: ```python for i in range(n): for j in range(i, n): # check window arr[i..j] ``` That inner loop is doing redundant work. When `i` advances from 3 to 4, most of the window `arr[3..j]` overlaps with `arr[4..j]`. The sliding window keeps that overlap alive and only processes the new element and the dropped element. ## Fixed window: the easy case first Fixed window problems give you the window size `k` upfront. "Maximum sum of any k consecutive elements" is the canonical one. The brute force recomputes the sum of each window from scratch — O(n·k). The insight: when you slide the window one step right, the new sum is just the old sum plus the incoming element minus the outgoing one. ```python def max_sum_fixed(arr, k): if len(arr) < k: return None # Build the first window window_sum = sum(arr[:k]) best = window_sum # Slide: add the new right element, subtract the element leaving on the left for right in range(k, len(arr)): window_sum += arr[right] # expand right window_sum -= arr[right - k] # shrink left (the element k steps behind) best = max(best, window_sum) return best ``` One pass, O(n), O(1) extra space. The key move — `arr[right - k]` is exactly the element that just fell off the left edge when the window advanced. Fixed windows are almost too simple once you see it. The interesting problems are variable. ## Variable window: expand right, shrink left Most interview sliding window problems do not give you `k`. Instead they give you a constraint and ask you to find the optimal window that satisfies it. The window has to breathe. The template is worth memorizing: ```python def variable_window(arr): left = 0 state = ... # running sum, counter dict, set, etc. best = 0 for right in range(len(arr)): # 1. Expand: include arr[right] in the window state = update(state, arr[right]) # 2. Shrink: while the constraint is violated, drop the left element while invariant_violated(state): state = remove(state, arr[left]) left += 1 # 3. The window [left, right] now satisfies the constraint. # Update the answer. best = max(best, right - left + 1) return best ``` The reason this is O(n) and not O(n²): each element is added to the window exactly once (when `right` passes over it) and removed at most once (when `left` catches up). Two total operations per element across the entire run — O(n) total, regardless of how many times the inner `while` fires. Let's make that concrete with two real problems. ## Worked problem 1: longest substring without repeating characters **Problem:** Given a string, find the length of the longest substring that contains no duplicate characters. The brute force checks all O(n²) substrings and scans each for duplicates — O(n³) total. Variable window gets it to O(n). **Invariant:** the window `s[left..right]` contains no character more than once. **State:** a set of the characters currently inside the window. ```python def length_of_longest_substring(s: str) -> int: seen = set() # characters in the current window left = 0 best = 0 for right in range(len(s)): # Shrink from the left until the new character fits while s[right] in seen: seen.remove(s[left]) left += 1 seen.add(s[right]) best = max(best, right - left + 1) return best ``` Walk through `"abcabcbb"`: - `right=0` ('a'): seen={a}, window="a", best=1 - `right=1` ('b'): seen={a,b}, window="ab", best=2 - `right=2` ('c'): seen={a,b,c}, window="abc", best=3 - `right=3` ('a'): 'a' is in seen — shrink. Remove 'a', left=1. Now 'a' not in seen. Add 'a', seen={b,c,a}, window="bca", best=3 - `right=4` ('b'): 'b' is in seen — shrink. Remove 'b', left=2. Add 'b', window="cab", best=3 - ... and so on. The answer is 3 ("abc"). Notice the `while` loop: when you hit a repeat, you keep shrinking — not just once. That while-not-just-if distinction is where most bugs hide. Here is the interesting moment of that trace — the shrink at `right=3` and the second one at `right=4`: ```mermaid flowchart TD A["right=2: window 'abc', seen={a,b,c}, best=3"] --> B["right=3: 'a' already in seen"] B --> C["shrink: remove s[0]='a', left=1"] C --> D["add 'a' → window 'bca', invariant restored, best stays 3"] D --> E["right=4: 'b' already in seen — shrink again, left=2"] E --> F["window 'cab' — each element enters and leaves at most once: O(n)"] style B fill:#ff2e88,color:#000 style C fill:#ffaa00,color:#000 style D fill:#22c55e,color:#000 style F fill:#0e7490,color:#fff ``` When a duplicate enters from the right, `left` has to chase it down — and it might have to move more than one step. That is exactly what the `while` guarantees. ## Worked problem 2: minimum window substring (sketch) This one is a classic hard problem that still reduces to the same template. Given a string `s` and a pattern `t`, find the smallest substring of `s` that contains all characters of `t` (including duplicates). The constraint is now more complex — not just "no repeats" but "contains the full frequency map of `t`." The state becomes a frequency counter, and you track how many distinct characters are currently satisfied. ```python from collections import Counter def min_window(s: str, t: str) -> str: need = Counter(t) # how many of each char we still need missing = len(t) # total characters still owed to the window best_start, best_len = 0, float('inf') left = 0 for right, c in enumerate(s): # Expand: if this character helps satisfy the constraint, decrement missing if need[c] > 0: missing -= 1 need[c] -= 1 # note: need[c] can go negative (we have surplus) # Shrink: once the constraint is met, try to tighten the left if missing == 0: # Move left as far as possible while still satisfying the constraint while need[s[left]] < 0: need[s[left]] += 1 left += 1 # Record this window if right - left + 1 < best_len: best_len = right - left + 1 best_start = left # Shrink one more step to break the constraint and keep searching need[s[left]] += 1 missing += 1 left += 1 return s[best_start : best_start + best_len] if best_len < float('inf') else "" ``` The structure is identical: expand right, check constraint, shrink left, record the best. The sophistication is in how you track the constraint — here a counter and a `missing` tally. Once you can read "expand right / shrink left / maintain invariant," you can adapt this skeleton to almost anything. ## The complexity picture | Approach | Time | Space | When | |---|---|---|---| | Brute force (nested loops) | O(n²) or O(n·k) | O(1) | Never, unless n < 100 | | Fixed sliding window | O(n) | O(1) | Window size k is given | | Variable sliding window | O(n) | O(1) | Optimal size is part of the answer; state is two indices and a running number | | Variable + hash map | O(n) | O(∣Σ∣) | Constraint involves character/element counts | The space `O(∣Σ∣)` for the hash-map variants is bounded by the alphabet or the set of distinct values — for ASCII strings that is at most 128, effectively constant. Compare the brute force and the variable window on the same input of n=10,000: - Brute force: ~50 million operations. - Sliding window: ~20,000 operations (two passes over 10,000 elements). That is a 2500x speedup from one insight. ## The classic bug: forgetting to shrink Here is a broken version of the longest-substring solution: ```python def broken_longest_substring(s: str) -> int: seen = set() left = 0 best = 0 for right in range(len(s)): if s[right] in seen: # BUG: if, not while seen.remove(s[left]) left += 1 seen.add(s[right]) best = max(best, right - left + 1) return best ``` The `if` instead of `while` only removes one character from the left when a duplicate appears. But what if the duplicate character is not the immediate left element? Trace it on `"abba"`: - `right=0` ('a'): not in seen. Add, seen={a}, best=1. - `right=1` ('b'): not in seen. Add, seen={a,b}, best=2. - `right=2` ('b'): 'b' is in seen — so we remove `s[left]` = `s[0]` = 'a' and set left=1. But 'a' was not the problem. Now seen={b} while the actual window `s[1..2]` = "bb" contains two b's. The state no longer describes the window. Corrupted. - `right=3` ('a'): 'a' is *not* in seen — we wrongly evicted it a step ago — so the `if` never fires. Add 'a', best = 3 − 1 + 1 = **3**. The function returns 3. The correct answer for `"abba"` is 2. No crash, no exception — just a confidently wrong number, which is the worst kind of bug to have in an interview. The fix is always `while`: keep removing from the left until the invariant actually holds, not just until you've done one removal. The invariant has to be true when you exit the shrink phase, and a single removal does not guarantee that. ## When sliding window is the wrong tool Sliding window requires that you can **add** and **remove** elements from the window state cheaply and that moving a pointer in one direction is always correct (no backtracking). Skip it when: - **The subarray does not have to be contiguous.** Non-contiguous subsets → dynamic programming or backtracking. - **The answer involves pairs or triplets that are not neighbors.** Sounds like [two pointers](/dsa/techniques/two-pointers) or sorting. - **The constraint is non-monotonic** — adding more elements can both satisfy and violate it. Classic example: "subarray with sum exactly k where elements can be negative." With negative numbers, a larger window is not necessarily worse, so you cannot decide greedily whether to shrink. Prefix sums and a hash map handle that case. - **The data is 2D.** You need extra machinery (collapse rows with prefix sums, then slide). The monotonicity check is the most important: ask yourself "if the current window violates the constraint, does extending it further help or hurt?" If extending always hurts, shrinking from the left is safe and sliding window applies. If extending *might* help (negative numbers, for instance), it does not. ## Patterns this unlocks Once the template is in your head, a surprising number of problems click: - **Max sum of k elements** — fixed window, running sum. - **Longest substring without repeating characters** — variable window, set. - **Minimum window substring** — variable window, frequency counter. - **Fruits into baskets / at most K distinct** — variable window, counter with distinct-key tracking. - **Longest subarray with ones after replacing at most k zeros** — variable window, count of zeros in window. - **Permutation in string** — fixed window of length `len(p)`, frequency counter comparison. Every one of these is the same skeleton with a different invariant slotted in. That is the power of pattern recognition — you are not solving 10 different problems, you are solving one problem with 10 different constraints. For problems where the window needs a max or min of the elements *inside* it (not just a sum), the window alone is not enough — pair it with a monotonic deque. But that is a technique for another day. ## Putting it together The next time you hit a problem that says "longest", "shortest", "minimum", or "maximum" over a contiguous range, do this: 1. Identify the **invariant** — what property must the window always satisfy? 2. Choose your **state** — sum, set, counter, whatever tracks that invariant cheaply. 3. Write the template: `for right in range(n)` → expand → `while violated` → shrink → record. 4. Check: is every element added once and removed at most once? If yes, you have O(n). That is it. The sliding window is not a clever trick so much as a disciplined way of not redoing work. Once you see it, you cannot unsee it — and you will see it everywhere. For related techniques, [two pointers](/dsa/techniques/two-pointers) solves a similar class of problems but with pointers moving from both ends toward the middle rather than a window moving in one direction. For the hash map and set internals used to maintain window state, see [hash table](/dsa/structures/hash-table). And if you are still fuzzy on why O(n) beats O(n²) by so much in practice, [Big-O](/dsa/crash-course/02-big-o-notation) has the concrete numbers. ## Frequently asked questions Q: What is the sliding window technique? A: The sliding window technique maintains a moving range [left, right] over a sequence and adjusts its boundaries to satisfy some constraint — without re-scanning elements already processed. The right pointer expands the window to include new elements; the left pointer shrinks it when the constraint is violated. Because each element is added and removed at most once, the whole pass is O(n) instead of the O(n²) you get from nested loops. Q: How do I know when to use a sliding window? A: Look for three signals: the problem asks about a contiguous subarray or substring; the question involves "longest", "shortest", "minimum", "maximum", or "contains"; and the data is linear (array or string). When you see a brute force with two nested loops where the inner loop starts from the outer index, that is almost always a sliding window in disguise. Q: What is the difference between a fixed and variable sliding window? A: A fixed window has a predetermined size k that never changes — you slide a k-wide frame one step at a time. A variable window has no fixed size; you expand it by moving right and shrink it by moving left until some invariant is satisfied. Most interview problems use variable windows because the optimal window size is part of what you are computing. Q: What is the most common sliding window bug? A: Shrinking only once — writing if instead of while when restoring the invariant. The algorithm still runs in O(n), but the window state gets corrupted the first time the offending element is not the immediate left neighbor, and the function returns a confidently wrong answer (on "abba" the broken version returns 3 instead of 2). The fix: after every right-pointer move, keep advancing left until the invariant holds again, not just once. Q: Can sliding window work on a 2D array or linked list? A: Sliding window is fundamentally a one-dimensional technique — it relies on two indices into a linear sequence. For 2D problems you can sometimes collapse a dimension (e.g., prefix-sum each column and then slide a window over the collapsed rows), but that is a different trick. Linked lists technically support two pointers, but without O(1) index access the window state updates become awkward; in practice you only see sliding window on arrays and strings.