Sliding window, from brute force to O(n)

Half of what feels like a hard interview problem is a sliding window in disguise. "Longest substring without repeats." "Subarray with sum K." "Minimum window that contains every character of T." All the same shape: a window that grows to admit a new element, then shrinks until the property you care about is restored, then grows again.

The pattern replaces most nested-loop brute forces with a single left-to-right scan. Here's the walk-through — brute force first, then the rewrite that lifts it into linear time, then a runnable snippet you can hit Run on.

The brute force

The obvious first pass: for every start index i, extend j until you hit a repeat, then reset. Correct — because you check every substring — wrong for anything real, because the inner loop re-scans work you already did.

Complexity is O(n²) time, O(n) space. On a 10⁴-character input that's a hundred million comparisons — a laptop can just about get through that, but you've wasted every re-scan.

Try it: paste abcabcbb when it prompts for stdin. Answer is 3 (the window abc). Paste bbbbb — answer is 1.

Grow, then shrink

The window is a pair of pointers, left and right. right only ever moves forward — that's the outer loop. left jumps forward when the invariant ("no repeats in the current window") would break, and never backwards.

The key observation: because each pointer moves forward at most n times across the whole scan, the total work is O(n) — not O(n) per step, O(n) total. The nested-loop shape has become a single pass with two pointers that meet somewhere on the right.

Same three example inputs, same three answers, but this version stays fast on inputs a hundred times bigger.

Same shape, over and over: grow the window; shrink until the invariant holds; measure. Once you spot it, half the "longest substring" and "shortest subarray" problems collapse into three-line variants of that skeleton.

Beyond substrings — subarray sums

The same pattern works when the invariant is "sum ≤ K" instead of "no repeats". Grow by adding to the running sum; shrink from the left when it exceeds K; measure the window whenever the invariant holds.

Paste 1 2 1 3 2 on line 1 and 4 on line 2. Answer is 3 — the subarray 1 2 1.

What to notice

Three signals that a problem is asking for a sliding window:

• "Longest / shortest / smallest / largest" window with some property → sliding window.
• Contiguous subarray or substring (not subsequences) → sliding window.
• The naive solution is a nested loop where the inner one starts from the outer index and only ever moves forward → sliding window.

If the naive inner loop restarts arbitrarily (e.g. binary search inside a walk), the pattern is different — likely two-pointer converging or a monotonic stack.

Try one more

Head to the problems index for more practice. The two-pointer walks (Reverse String, Valid Parentheses) build the same intuition of "two indices, always moving forward" — read those next if the pattern hasn't clicked yet.

If you have questions or spot a bug in one of the snippets, send us a note.