Sliding Window

A sliding window is a contiguous range bounded by two indices that only ever move forward, plus a small amount of state describing what is currently inside it. It is the specialised form of two pointers that appears often enough — and has enough variants — to be worth its own page.

The problems it solves all look the same once you see it: find the best contiguous stretch satisfying some condition. The brute force enumerates every stretch, which is O(n²) substrings each costing O(n) to check. A window gets the same answer in one pass.

The two templates#

Almost every sliding-window problem is one of two shapes, and picking the wrong one is the main way people get stuck. The difference is a single word.

Looking for the longest valid window — grow the right edge always, and shrink from the left while the window is invalid. Every time the loop reaches the bottom, the window is valid, so that is where you record.

lo = 0
for hi = 0 .. n - 1:
    add a[hi] to the window

    while window is INVALID:
        remove a[lo]; lo = lo + 1

    best = max(best, hi - lo + 1)      // valid here, by construction

Looking for the shortest valid window — grow the right edge until the window becomes valid, then shrink while it stays valid, recording as you go. The last valid size before it breaks is the best that right edge can offer.

lo = 0
for hi = 0 .. n - 1:
    add a[hi] to the window

    while window is VALID:
        best = min(best, hi - lo + 1)  // record BEFORE shrinking
        remove a[lo]; lo = lo + 1

That is the whole distinction: shrink while invalid to maximise, shrink while valid to minimise. Note where the recording sits — outside the loop in the first, inside it in the second. Getting that wrong produces answers that are off by exactly one shrink.

Step through it and watch the two phases alternate. While the window is missing something, the left edge is frozen — shrinking an invalid window cannot help, it can only make it worse. The moment it becomes valid, the roles swap and the left edge does all the moving, trimming slack until removing one more character would break it.

Why the inner loop is not a second pass#

Both templates have a while inside a for, which reads as O(n²) and is not.

lo never decreases. Across the entire run it advances at most n times in total, no matter how those moves are distributed between iterations — one iteration might shrink five times and the next none at all. The two edges together perform at most 2n moves, so the whole scan is O(n), amortised.

This is the same argument that makes a monotonic stack linear, and it is worth being able to state, because “there’s a nested loop but it’s still O(n), because the left pointer only moves forward” is exactly what an interviewer is listening for.

The state is the problem#

The template is fixed. What changes between problems is the state you carry and what makes a window valid — and that is where the actual thinking goes.

• A count of distinct items — a hash map from item to how many are in the window. Valid when the map has at most k keys.
• A set — for “no repeated characters”, membership is all you need. Longest Substring Without Repeating Characters is this, and the window shrinks until the duplicate is gone.
• A running sum — add on the way in, subtract on the way out. Valid when the sum is under a limit.
• A satisfied counter — for Minimum Window Substring. A map alone is not enough, because comparing two maps on every step would be O(k) per move. Instead keep a single number: how many of the required characters currently have enough copies. It changes by at most one per add or remove, so validity is one integer comparison.

That last one is the trick worth taking away. Reduce validity to a number you can update in O(1), rather than a condition you have to re-evaluate. If checking your window costs O(k), the whole scan is O(nk) and you have given back most of what the window bought.

Both directions must be symmetric: whatever adding an element does to the state, removing it must exactly undo. Most sliding-window bugs are an add and a remove that do not mirror each other — a counter incremented on the way in but not decremented on the way out, or a “satisfied” count that only goes up.

Fixed-size windows#

When the window length is given rather than discovered, there is no shrink loop at all. Slide one position at a time: add the entering element, remove the leaving one, and check.

for hi = 0 .. n - 1:
    add a[hi]
    if hi >= k:
        remove a[hi - k]        // keep exactly k in the window
    if hi >= k - 1:
        check the window

Find All Anagrams in a String is this with a frequency count of size 26: the window is an anagram exactly when its counts match the pattern’s. Comparing 26 counts on every step is technically O(26) rather than O(1), which is fine — but the same “satisfied counter” trick reduces it to one comparison if you want it.

The off-by-one to watch is hi >= k - 1 for the first complete window against hi >= k for the eviction. They differ by one, deliberately.

When a window does not apply#

Two conditions have to hold, and it is worth checking both before writing the loop:

• The answer must be contiguous. A window cannot skip elements. If the problem allows gaps, it is probably dynamic programming or a prefix sum.
• Validity must be monotonic in the window’s size — if a window is invalid, every larger window containing it must also be invalid. That is what makes shrinking a sound response. Negative numbers break this for sum-based conditions: extending a window can lower the sum, so “shortest subarray with sum ≥ k” over negative values is not a sliding-window problem at all, and needs prefix sums with a deque instead.

That second condition is the one people skip. If a window can become valid again by growing, after having been invalid, the template is unsound no matter how the code is arranged.

Recognising it#

Reach for a sliding window when:

• The answer is a contiguous subarray or substring, and you want the longest, shortest, or a count of them.
• The problem says “at most k”, “exactly k”, or “containing all of”. The first is a window directly; the second is usually at most k minus at most k−1, run twice.
• The brute force is “for every start, extend to every end”, and extending changes the answer predictably.
• A fixed length is given — that is the simplest form, and the shrink loop disappears.

And the two checks before committing: is the answer contiguous, and does invalid stay invalid as the window grows?

Summary#

Two forward-only edges and a running description of what lies between them. Grow on the right always; shrink on the left while invalid to find the longest, or while valid to find the shortest — and record in the matching place. The nested loop is linear because the left edge never turns around. The template is not the work: the work is choosing state that makes “is this window valid” a single O(1) check, and making sure that adding and removing an element are exact mirrors of each other.