Sliding Window
- State the three properties that make a problem solvable by sliding window: contiguity, incrementally maintainable state, and predictable validity
- Classify any contiguous-subarray problem into one of four template families and explain why each template places the update where it does
- Reconstruct the expand/shrink/update loop from first principles and explain why it runs in O(n)
- Recognize when sliding window fails and name the correct alternative technique
Sliding window maintains a running state over a contiguous range and updates it incrementally as two boundaries move through the data, reducing O(n²) brute force to O(n). This guide builds the technique from three core properties, walks through a canonical problem, then derives four template families from the same skeleton. Each section ends with a reconstruction check so you can verify your understanding before moving on.
The Sliding Window Invariant
Sliding window applies when a problem has three properties. If any one fails, the technique breaks. Understanding why each property is necessary matters more than memorizing templates.
Vocabulary you need first
This guide uses a few terms repeatedly. Here is what each one means concretely:
"valid window" A window [left, right] that satisfies the problem's constraint right now. Example: if the constraint is "at most 2 distinct characters," then [a, b, a] is valid and [a, b, c] is not.
"invalid window" A window that violates the constraint. You must shrink it before recording an answer.
"at most k" The tracked quantity must be ≤ k. Example: "at most 2 distinct characters" means the window is valid when distinct count ≤ 2. Growing the window can push you over k (invalid). Shrinking can bring you back under (valid).
"at least target" The tracked quantity must be ≥ target. Example: "sum ≥ 7" means the window is valid when sum ≥ 7. Growing the window can make you reach the target (valid). Shrinking can drop you below (invalid).
"exactly k" The tracked quantity must equal k exactly. This usually cannot be solved with a single sliding window pass. See Section 6.
Property 1: The Answer Is a Contiguous Range
The answer is a contiguous range [left, right]. Every element between the two boundaries is part of the window. If you could skip elements, sliding window cannot enforce which elements are included, and you need a different technique (two pointers on sorted data, DP for subsequences, or hash map for arbitrary pairs).
Elements at indices 0, 1, 2
Property 2: O(1) State Updates
Adding or removing one element from the window boundary updates the tracked state in O(1). This is what makes the technique O(n) instead of O(n²). If recomputing state after each boundary move costs O(k) for window size k, you are back to brute force.
This table summarizes what state to track for common constraint types. If a row is not obvious, read the corresponding template in Section 4 first, then come back.
| Constraint | What to track | Data structure | Why O(1) |
|---|---|---|---|
| Sum constraints (nonneg) | Running sum | int | Adding/removing one element is one arithmetic op |
| No duplicates | Elements in window | set | O(1) add, remove, membership test |
| At most k distinct | Count of each element | dict / Counter | Each add/remove is O(1). len(dict) equals distinct count only if you delete keys when their count hits zero |
| Contains all chars of t | Char counts + formed count | dict + int | formed tracks how many chars meet their quota |
| At most k zeros | Zero count | int | Increment on 0 entry, decrement on 0 exit |
Property 3: Growing the Window Can Only Hurt, Shrinking Can Only Help
Ask yourself: "When I add one more element on the right, does the tracked quantity move in one predictable direction?" For "at most 2 distinct characters," adding a character can only increase the distinct count (or keep it the same). It can never decrease it. That means growing the window can only push you toward invalidity, never toward validity. Conversely, removing an element from the left can only decrease the distinct count, moving you back toward validity.
This one-directional behavior is what makes the shrink loop work. The loop can always restore validity by shrinking, and it never needs to re-expand. Some resources call this property "monotonicity." The label does not matter. What matters: if growing can both help and hurt (as with negative numbers in a sum), the shrink loop cannot guarantee progress, and sliding window breaks.
When this property fails (e.g., negative numbers in a sum constraint), shrinking can increase the tracked quantity instead of decreasing it. The shrink loop no longer moves toward validity, and the algorithm skips valid windows or loops indefinitely.
The Generic Skeleton
Every sliding window solution fills the same three-step loop. The three properties above are what make this loop correct: the range must be contiguous, each step updates state in O(1), and shrinking always moves toward validity.
Note: For shortest problems, the update happens inside the shrink loop. See Template 3 in Section 4.
Spotting the Three Properties in Problem Statements
"contiguous subarray", "substring", "consecutive", "window"
Signals Property 1. The answer is a continuous slice [left, right].
"at most k", "at least k", "exactly k", "sum ≤ target"
Signals Property 3. Ask: does adding one more element make the constraint harder to satisfy? For "at most k distinct," adding an element can only increase distinct count, never decrease it. That one-directional pressure is what you need. If the constraint can get easier or harder unpredictably when growing, sliding window will not work.
"longest", "shortest", "count", "of size k"
Tells you which template to use. "Longest" means shrink while invalid, update after (Template 2). "Shortest" means shrink while valid, update inside (Template 3). "Count" uses the same structure as longest but accumulates right - left + 1 (Template 4). "Of size k" means fixed window, no shrink decision (Template 1).
"nonnegative integers", "positive numbers"
Confirms Property 3 for sum-based constraints. If negatives are present, sliding window on sums fails.
The Pattern in Action
Fixed-Window Warm-Up
Problem: Given [2, 1, 5, 1, 3, 2], find the maximum sum of any 3 consecutive elements. The window size is given, so there's no shrink decision. Just slide and update.
Fixed Window (k=3)
Step 1 of 8 · Sum the first k=3 elements: 2 + 1 + 5 = 8. This initial sum is the foundation. Every future slide updates it instead of recomputing from scratch.
When the window size is not given, the algorithm must decide when to shrink. That decision is what distinguishes the four template families.
Brute Force: Why O(n²) Is Wasteful
The naive approach checks every possible subarray:
Moving from subarray [1,2,3] to [1,2,3,4] reprocesses three elements that were already in the previous window. Only one element changed, but brute force recomputes the entire range.
Worked Example: Longest Substring Without Repeating Characters
Problem: Given "abcabcbb", find the length of the longest substring without repeating characters.
Variable Window (Expand & Shrink)
Step 1 of 15 · Invariant: the set tracks every unique char in [L..R]. "a" is new, so add it and expand.
Why This Is O(n), Not O(n²)
The while loop inside the for loop looks like it could be O(n) per iteration, giving O(n²) total. It is not. Each index enters the window exactly once (when right advances) and leaves at most once (when left advances past it). Total pointer moves across the entire run:
When the Invariant Breaks
Property 3 is the one that breaks most often. The clearest example: negative numbers in a sum constraint.
Failure Case: Negative Numbers
Consider [1, -1, 2, 3] with target sum 4. The shrink loop assumes that removing the leftmost element decreases the sum, moving toward validity. But removing the -1 at index 1 increases the sum from 4 to 5. The algorithm moves left past valid windows without recording them.
Shrinking the window should never increase the sum. Negative numbers break that guarantee.
Here's why: shrinking removes a negative, which increases the sum instead of decreasing it. Property 3 requires that shrinking always moves the tracked quantity toward the "not violating" side. With negatives, shrinking can move it in either direction, so the algorithm can't make progress.
Alternative: Prefix sums + hash map. Convert each subarray sum to currentPrefix - earlierPrefix, and use a hash map to count how many earlier prefixes produce the target difference. This avoids the monotonicity requirement entirely.
Other Failure Modes
Non-contiguous elements: Property 1 fails. If elements don't need to be adjacent (e.g., "longest increasing subsequence"), use DP or binary search.
Expensive state updates: Property 2 fails. If recomputing state costs O(k) per step (e.g., "is this window a palindrome?"), you lose the O(n) advantage and are back to brute-force territory.
The Four Template Families
Every sliding window solution fills the same skeleton. What changes between templates: the goal, the shrink condition, and where the update goes.
Template 1: Fixed Size Window
The window size k is given. No shrink decision needed.
No while loop because the window size never changes. The outgoing index is always right - k. A running sum suffices because each step changes exactly two elements.
Template 2: Variable Window (Find Longest)
Maximize window length under an "at most" constraint. Example: longest substring with at most k distinct characters.
The shrink loop uses while not if because a single violation may require removing multiple elements before validity is restored. The update goes after the shrink loop because the window must be valid before measuring its length.
Why frequency map, not set: A set tells you what is present but not how many of each. When a character leaves the window, you need the count to know whether it is still present elsewhere in the window. Only when the count drops to zero do you delete the key and reduce the distinct count.
Template 3: Variable Window (Find Shortest)
Minimize window length under an "at least" constraint. Example: minimum size subarray with sum >= target.
The shrink condition is while valid, not while invalid. Every valid window is a candidate, and shorter valid windows are better, so the algorithm keeps shrinking as long as validity holds. The update goes inside the loop because each iteration starts with a valid window that might be the answer. The condition uses >= not > because a window with sum exactly equal to target is still valid.
See it in action: Minimum Window Substring
Given string s and target t, find the smallest window in s containing all characters of t. Expand until valid, then shrink while still valid, recording the candidate at each shrink step:
Minimum Window Substring · target = "ABC"
Build two hash maps: "need" tracks required counts for A, B, C and "have" tracks current counts. The "formed" counter increments when a character meets its required count.
Template 4: Counting Valid Subarrays
Count how many subarrays satisfy an "at most" constraint. Example: count subarrays with at most k distinct elements.
After shrinking, [left, right] is the longest valid window ending at right. Every subarray [i, right] where left ≤ i ≤ right is also valid, because removing elements from the left cannot violate an "at most" constraint. The count can only stay the same or go down. That yields exactly right - left + 1 valid subarrays ending at right.
This reasoning applies only to "at most" constraints. For "exactly k", shorter windows can drop below k, so the counting formula does not apply directly.
Longest vs Shortest
Templates 2 and 3 share the same skeleton but differ in two critical places: the shrink condition and the update placement. Swapping either one produces code that silently returns wrong answers.
| Find Longest | Find Shortest | |
|---|---|---|
| Shrink condition | while invalid. Shrink only until the constraint is satisfied again | while valid. Keep shrinking as long as the window still meets the constraint |
| Update placement | After shrink loop | Inside shrink loop |
| Initialization | best = 0 | best = float('inf') |
| Goal of shrinking | Restore validity. You want the longest window, so shrink only until valid again. Any further would make it shorter than necessary | Search for the minimum. You want the shortest valid window, so keep shrinking while still valid. Each shrink is a potentially better answer |
Code Comparison
The shrink condition is while invalid(). The window shrinks only until it becomes valid again. The update (best = max(...)) happens after the shrink loop, when the window is guaranteed valid.
while invalid instead of while valid. Shrinking while invalid in a shortest problem means you only shrink past the answer, never recording it.Counting vs Optimizing
The counting template is structurally identical to Find Longest with one change: replace best = max(best, ...) with result += right - left + 1. Both shrink while invalid, both update after the shrink loop. The only difference is accumulation instead of maximization.
Counting Subarrays · k = 2 distinct
Window [1] has 1 distinct, which is <= k=2. The key counting insight: every valid window [L..R] contributes (R-L+1) subarrays, one for each possible start point from L to R. Here that is 1.
The "Exactly K" Problem
Counting subarrays with exactly k distinct elements cannot use the counting template directly. The counting template relies on a key property: if a window [left, right] is valid under an "at most k" constraint, then every shorter window [i, right] where left <= i <= right is also valid, because removing elements can only decrease the distinct count. For "exactly k," that property fails. Consider the array [1, 2, 1] with k = 2. The window [0, 2] has 2 distinct elements (valid). But the sub-window [2, 2] = [1] has only 1 distinct element (invalid). Shorter windows can drop below k, so the right - left + 1 formula counts windows that are not all valid.
The solution splits "exactly k" into two "at most" passes:
Here is why this works. atMost(k) counts every subarray with 0, 1, 2, ..., or k distinct elements. atMost(k-1) counts every subarray with 0, 1, 2, ..., or k-1 distinct elements. Every subarray counted by atMost(k) but not by atMost(k-1) must have exactly k distinct elements. It has at most k (so it is in the first set) but more than k-1 (so it is not in the second). The difference isolates exactly k. Each atMost pass is a standard counting template, so the total work is two O(n) passes.
exactly(k) = atMost(k) - atMost(k-1) always holds when atMost is a function that can only stay the same or increase as k increases.Sliding Window vs Other Techniques
7a: Sliding Window vs Two Pointers
Both use two indices. The distinction: sliding window tracks aggregate state across a range, while two pointers compare or coordinate values at two positions.
| Sliding Window | Two Pointers | |
|---|---|---|
| What indices represent | Boundaries of a range. Everything inside matters | Two positions being compared or coordinated |
| What you track | Aggregate state between pointers (sum, counts, set) | Relationship between elements at the pointers (sum, distance) |
| Movement | Right always advances. Left catches up on violation | Either pointer moves based on comparison |
| Typical input | Unsorted array or string | Often sorted array, but also linked lists and partitioning problems |
Sliding Window vs Two Pointers
Sliding Window
All elements between pointers matter
Window slides as a unit
Two Pointers
Only values at endpoints matter
Pointers move independently
Step 1 of 6
| Problem | Pattern | Why |
|---|---|---|
| "Longest substring without repeating chars" | Sliding window | Tracking all chars in range [left, right] |
| "Two sum in sorted array" | Two pointers | Comparing arr[left] + arr[right] to target |
| "Container with most water" | Two pointers | Comparing heights at left and right |
| "Minimum window substring" | Sliding window | Tracking char counts in range |
| "3Sum" | Two pointers (inner loop) | Finding pairs that sum to complement |
Ask yourself these two questions:
- "Am I tracking everything inside a range, or only comparing values at two positions?" If you need aggregate state (sum, count, set of elements) across all elements between the pointers, that is sliding window. If you only care about the values at the two pointer positions, that is two pointers.
- "Does my input need to be sorted for the logic to work?" Two pointers on sorted data is a strong signal. Sliding window almost never requires sorted input.
7b: Sliding Window vs Prefix Sums
Both handle subarray queries in O(n). The choice depends on whether the constraint is monotonic and whether negatives are present.
| Sliding Window | Prefix Sums + Hash Map | |
|---|---|---|
| Works with negatives | No (breaks monotonicity) | Yes |
| Constraint type | "at most", "at least" (monotonic) | "exactly k", any sum target |
| Space | O(1) to O(alphabet) | O(n) for prefix map |
| When to choose | Nonneg + at-most/at-least | Negatives present, or exact-sum needed |
Ask yourself: "Can the array contain negative numbers?" If yes, sliding window on sums fails because shrinking can increase the sum instead of decreasing it. Use prefix sums + hash map. If the array is nonnegative and the constraint is "at most" or "at least," sliding window is simpler and uses less space.
7c: Sliding Window vs Center Expansion
"Longest palindromic substring" looks like a window problem. It's contiguous. It's an optimization over substrings. But Property 2 fails: you cannot update "is palindrome" in O(1) when one element enters or leaves a boundary. Adding a character to the right doesn't tell you anything about whether the extended string is palindromic without checking the matching character on the other end. Use center expansion (O(n²)) or Manacher's algorithm (O(n)).
Quick Recognition Table
| Problem | Technique | Reason |
|---|---|---|
| "Max sum of k consecutive elements" | Sliding window (fixed) | Contiguous range, window size given explicitly, sum updates in O(1) per step |
| "Longest substring without repeats" | Sliding window (longest) | Substring = contiguous range. "No repeating" is an at-most constraint (at most 1 of each char). Set membership is O(1) |
| "Two numbers that sum to target" | Two pointers / hash map | Not a contiguous range. You pick two positions anywhere. No window state to maintain |
| "Subarray sum = k" with negatives | Prefix sums + hash map | Negatives mean shrinking can increase the sum, breaking Property 3. Prefix sums avoid this problem |
| "Min window containing all of t" | Sliding window (shortest) | Contiguous range with an "at least" constraint (contain all of t). Char count updates are O(1) |
| "Longest palindromic substring" | Center expansion / DP | Adding one character to a boundary tells you nothing about palindrome-ness without checking the opposite end. Property 2 fails |
| "Count subarrays with sum = k" (nonneg) | Sliding window (counting) | Contiguous range, nonnegative values preserve monotonicity, and the goal is counting (not optimizing) |
Advanced: Monotonic Deque
The fixed-window template assumes O(1) state updates. For sums, that works: add the new element, subtract the old. But for max or min over a window, removing the current maximum does not reveal the second-largest without rescanning the window. That costs O(k) per step, making the algorithm O(nk).
The monotonic deque solves this. "Monotonic" means the values in the deque are always in decreasing order (for max problems) or increasing order (for min problems). The deque stores indices of elements that could still become the window's maximum. It maintains decreasing order by popping any element from the back that is smaller than the new element. Those popped elements will never become the window maximum. The new element is both larger and newer, so it will remain in the window longer than any of them.
Problem: Given an array and window size k, return the maximum value in each window position as it slides left to right.
Monotonic Deque (k=3)
Step 1 of 17 · Goal: maintain a deque of candidate indices in decreasing value order. The front is always the window max.
Every index in the deque corresponds to a value that could still become the window maximum. When a new element enters, any element already in the deque with a smaller value will never become the maximum, because the new element is both larger and newer. Pop those from the back. When the window slides forward, any index outside the window boundary is no longer valid. Pop those from the front. After both operations, the front of the deque holds the current window maximum.
Common Pitfalls
Bug 1: Window Never Shrinks
The trap: This code never moves left. The set grows to include every character in the string, and best measures the entire string regardless of duplicates. On "abcabcbb", it returns 8 instead of 3 because the window [0, 7] contains repeated characters but is never shrunk.
Fix: The shrink loop must run before measuring. When s[right] is already in seen, remove characters from the left until the duplicate is gone, then add s[right] and measure:
Bug 2: Off-by-One in Window Size
The trap: A window from index 2 to index 5 contains 4 elements, not 3. Inclusive ranges always have end - start + 1 elements. Writing right - left undercounts by one, which typically makes every answer exactly one less than correct.
Fix: Use right - left + 1.
Bug 3: Not Deleting Zero-Count Keys
The trap: After decrementing count[s[left]], the key still exists in the dictionary with value 0. len(count) counts that key, so the distinct count stays inflated even though the character is no longer in the window. The shrink loop keeps running past where it should stop, or the window stays flagged as invalid when it is actually valid.
Fix: Delete the key when its count reaches zero so that len(count) accurately reflects the number of distinct characters currently in the window:
Bug 4: Wrong Shrink Direction
The trap: Find Shortest problems require shrinking while the window is valid, not while it is invalid. Writing while window_sum < target shrinks when the window is invalid (sum below target), which moves left forward when the sum is already too small. That is exactly backwards.
Fix: Every valid window is a candidate answer, and shorter valid windows are better, so you keep shrinking as long as validity holds. The correct condition is while window_sum >= target. Record the candidate length, then shrink to search for something shorter:
Bug 5: Uninitialized State
The trap: Python raises UnboundLocalError (or in other languages, uses garbage or zero). The window sum accumulates incorrectly from the first iteration, and best may never update correctly.
Fix: Initialize window_sum = 0 and best = 0 (or float('-inf') if values can be negative) before the loop.
Bug 6: Wrong Data Structure
The trap: List membership (x in list) scans every element, costing O(n) per check. Inside the shrink loop, this turns the O(n) algorithm into O(n²). This is exactly the failure that Property 2 warns about. Without O(1) state updates, the linear-time guarantee disappears.
Fix: Use set() for O(1) membership.
Edge Cases to Always Check
Empty array
If the array has no elements, the for loop never runs. Return 0 or an empty result. The danger is accessing arr[0] or initializing state from the first element before checking length.
k = 0
For "at most 0 distinct" or "window of size 0," the shrink condition is immediately true and left can advance past right if you are not careful. Guard against this: if k equals 0, return 0 without entering the loop, or ensure your shrink loop handles the case where left > right.
k larger than the array
The window never needs to shrink because the constraint is never violated. If your code assumes at least one shrink happens (for example, uses left after the loop without checking), it may return wrong results. The entire array is the answer.
All elements identical
The window may grow to the full array without ever triggering the shrink loop. If your logic depends on shrinking happening at least once (for example, initializing best inside the shrink loop only), it never updates the answer.
No valid window exists
For "find shortest" with best initialized to float('inf'), if no window ever satisfies the constraint, best stays at infinity. Check for this before returning and convert to 0 or -1 as the problem requires.
Single element
The window is [0, 0] with size 1. If your off-by-one calculation gives size 0, this catches it. Also tests whether your initialization handles the case where left equals right.
Practice Problems
Problems are organized by template type. Fixed Window is the simplest (window size is given, no shrink decision). Find Longest and Find Shortest differ only in shrink direction and update timing. Counting builds on Find Longest by accumulating valid subarray counts at each position.
Fixed Window
| Problem | Difficulty | Approach |
|---|---|---|
| Maximum Sum Subarray of Size K | Easy | Slide a window of exactly size k. Add incoming element, subtract outgoing. Track max sum as window moves. |
| Maximum Average Subarray I | Easy | Same as max sum but divide by k at the end. Track sum, not average, to avoid floating point during iteration. |
| Contains Duplicate II | Easy | Window = set of elements within k distance. If new element already in window, duplicate found. Remove oldest when window exceeds k. |
| Sliding Window Maximum | Hard | Monotonic deque: keep indices of potentially-maximum elements in decreasing order. Remove from front when out of window, remove from back when smaller than current. |
Variable Window: Find Longest
| Problem | Difficulty | Approach |
|---|---|---|
| Longest Substring Without Repeating Characters | Medium | Expand right, track char positions in map. When duplicate found, shrink left past the previous occurrence. Update max after shrinking. |
| Longest Substring with At Most K Distinct | Medium | Expand right, track char frequencies. When distinct count exceeds k, shrink left until count <= k. Update max when valid. |
| Longest Repeating Character Replacement | Medium | Track frequency of most common char in window. If window_size - max_freq > k, shrink. The rest can be replaced. |
| Max Consecutive Ones III | Medium | Reframe: longest window with at most k zeros. Expand right, count zeros. When zeros > k, shrink left. Update max when valid. |
| Fruit Into Baskets | Medium | Longest subarray with at most 2 distinct elements. Same pattern as "at most k distinct" with k=2. |
Variable Window: Find Shortest
| Problem | Difficulty | Approach |
|---|---|---|
| Minimum Size Subarray Sum | Medium | Expand until sum >= target. Then shrink while still valid, updating min at each step. Update before shrinking, not after. |
| Minimum Window Substring | Hard | Track required char counts. Expand until all required chars satisfied. Shrink while valid, updating min. Use "formed" counter to avoid rechecking all chars. |
Counting
| Problem | Difficulty | Approach |
|---|---|---|
| Subarrays with K Different Integers | Hard | Exactly k = atMost(k) - atMost(k-1). Each atMost(k) is a "find longest" variant that counts all valid subarrays ending at each position. |
| Count Number of Nice Subarrays | Medium | Reframe: subarrays with exactly k odd numbers. Use atMost(k) - atMost(k-1). Or use prefix sum approach with hash map. |
| Binary Subarrays With Sum | Medium | Subarrays summing to exactly goal. Use atMost(goal) - atMost(goal-1). Each atMost counts subarrays with sum <= target. |
Test Your Understanding
10 questions covering sliding window patterns and edge cases.
Practice this pattern
Apply the guide to complete interview problems with explanations and code.
Learn Sliding Window in a guided sequence
The Interview Course connects this pattern to its prerequisites, worked lessons, and progressively harder problems.