Sliding Window Pattern

All lessons

Learn when the answer lives in a contiguous range whose size changes as you scan — and how to expand/shrink it in amortized O(n) instead of re-checking every subarray.

0/5 practice problems solved

Skip to practice

Recognizing the pattern

Reach for it when you need to

the problem asks about a contiguous subarray or substring;
a brute-force solution checks every (start, end) pair — O(n²) or worse;
there's a condition you can check incrementally as the window grows or shrinks (a count, a sum, a set of seen characters);
"longest/shortest/count of subarrays that satisfy X" is in the prompt.

Don't use it when

The range isn't contiguous — that's usually a hash map or DP problem, not a window.
Both ends move independently toward each other rather than the window resizing — that's Two Pointers.
The condition can't be checked incrementally (requires re-scanning the whole window on every step) — the window trick provides no speedup then.
Input is sorted and the question is about position, not a contiguous run — Binary Search likely fits better.

Core mental model

Keep a window [left, right) that always satisfies (or is being repaired toward) the problem's condition. Grow right to include one more element and update the window's running state; when the condition breaks, shrink left — never restart from scratch — until it's valid again. Because left only moves forward, the total work across the whole scan is still O(n), even though it looks like nested movement.

Typical time: O(n)

Typical space: O(k) or O(1)

Brute-force subarrays: O(n²) or O(n³)

Visual trace

Longest Substring Without Repeating Characters, s = "abcabcbb". Grow right; when a repeat enters the window, shrink left past the previous occurrence.

right = 2: window "abc" — All three characters are unique. Window length 3 is the best so far.

right = 3: 'a' repeats — 'a' is already in the window at index 0, so left jumps to index 1 (just past the old 'a').

Worked example: Longest Substring Without Repeating Characters

s = "abcabcbb". Track the last seen index of each character to know exactly how far to shrink.

Step-by-step trace of Longest Substring Without Repeating Characters
right / char	last seen at	left after shrink	window length
Key step: 2 / c	—	0	3
3 / a	0	1	3
6 / b	4	5	2

Invariant: At every step, the window [left, right] contains no repeated character; left is always one past the most recent duplicate seen so far.

Reusable template

The shape to adapt for a new problem in this pattern.

python

def solve(s):
    last_seen = {}
    left = 0
    best = 0
    for right, ch in enumerate(s):
        if ch in last_seen and last_seen[ch] >= left:
            left = last_seen[ch] + 1
        last_seen[ch] = right
        best = max(best, right - left + 1)
    return best

Common mistakes

Shrinking left one step at a time in a while loop instead of jumping directly to last_seen[ch] + 1 — both are correct and both are linear overall (left never moves backward), but the direct jump does fewer operations for last-seen-index problems like this one.
Forgetting to guard last_seen[ch] >= left, which lets a stale index outside the window incorrectly shrink it.
Recomputing the window's condition from scratch on every step instead of updating it incrementally.
Confusing this with Two Pointers: here the window resizes; there, two independent indices converge.
Off-by-one length math — window length is right - left + 1, not right - left.

Practice: easy → medium → timed check

Solve in order; each step adds one decision to the same pattern.

1. Best Time to Buy and Sell Stock
Easy
Not solved yet
Track a running minimum
Solution for Best Time to Buy and Sell Stock Practice Best Time to Buy and Sell Stock
2. Longest Substring Without Repeating Characters
Medium
Not solved yet
Shrink past the last duplicate
Solution for Longest Substring Without Repeating Characters Practice Longest Substring Without Repeating Characters
3. Minimum Size Subarray Sum
Medium
Not solved yet
Shrink while a sum condition holds
Solution for Minimum Size Subarray Sum Practice Minimum Size Subarray Sum
4. Sliding Window Maximum
Hard
Not solved yet
Monotonic deque inside the window
Solution for Sliding Window Maximum Practice Sliding Window Maximum
5. Minimum Window Substring
Hard
Not solved yet
Shrink while a coverage condition holds
Solution for Minimum Window Substring Practice Minimum Window Substring

Final timed check

Run a 30-minute mock covering this pattern; state the invariant before coding, then finish with complexity and edge cases.

Start timed mock

Next lesson

Binary Search

Continue