Sliding Window: turning O(n²) into O(n)

01 · Foundation

The brute-force baseline, and the shortcut

Take "longest substring without repeating characters," or "maximum sum of any window of size k." The naive approach is to check every possible contiguous window: there are roughly n starting points and up to n possible lengths, and if computing "is this window valid?" or "what's its sum?" from scratch takes its own O(n) pass, you land at O(n²) or worse before you've written a single optimization.

Here's the shortcut. When a window slides one step to the right, almost nothing about its contents actually changes — exactly one element leaves (whatever sat at the old left edge) and exactly one element enters (whatever sits at the new right edge). Everything in between is untouched. So instead of recomputing the window's sum, count, or validity from nothing, you update a small piece of running state: undo the contribution of what left, add the contribution of what just entered. That update is O(1), and it's the entire reason sliding window beats brute force.

02 · Two flavors

Fixed-size vs. variable-size windows

Every sliding window problem is one of two shapes, and telling them apart early saves a lot of confused debugging.

• Fixed-size — the window length is handed to you upfront, e.g. "the maximum sum of any window of size k." You slide a window of exactly that length one position at a time: one element enters on the right, one leaves on the left, every single step.
• Variable-size — the length is what you're actually solving for. The window expands by pushing right forward as long as it stays valid; the moment it becomes invalid, you shrink from left until it's valid again; then you keep expanding. This is the shape behind "longest substring without repeating characters."

A quick tell: if the problem statement hands you an explicit window length, it's fixed-size. If it asks you to find the longest/shortest/best window such that some condition holds, it's variable-size.

03 · Method

A repeatable framework

The same five decisions apply whether you're computing a sum, a count, or a maximum.

1. 1 Decide fixed or variableDoes the problem give you a length (fixed), or ask you to find the best length (variable)?
2. 2 Define "valid" preciselyWhat exact condition makes the current window acceptable — no duplicate characters, sum ≤ target, at most k distinct values?
3. 3 Expand rightMove the right pointer forward, updating whatever running state you track — a count map, a running sum, a deque — as each new element enters.
4. 4 Shrink left when invalidFor variable-size windows: only move left when the window becomes invalid, undoing that element's contribution to your running state as it leaves.
5. 5 Update the answer at the right momentUsually right after confirming the window is valid — not on every single expansion, or you'll record windows that were never actually valid.

04 · Worked example

Longest Substring Without Repeating Characters, on "abcabcbb"

Variable-size window. State: a map of each character's most recent index, plus left, the start of the current window. Rule: whenever right lands on a character already present in the window, jump left to just past that character's previous occurrence — not one step, straight there. Track the longest valid window seen so far.

The first three steps just grow the window — no repeats yet, so max len climbs to 3. At right=3 ('a'), the window already contains an 'a' at index 0, so left jumps to 1 (not 0+1 by coincidence — it's genuinely "one past the previous occurrence"). The same jump happens at right=6, where 'b''s previous occurrence was at index 4, so left jumps from 3 straight to 5, skipping over index 4 entirely rather than creeping forward one step at a time. From that point on every window is length ≤ 3, so the answer never improves again. Final answer: 3, the substring "abc".

Open the Longest Substring visualizer to watch this exact trace animate, character by character.

05 · Advanced technique

The monotonic deque trick — Sliding Window Maximum

"Maximum in every window of size k" looks like it needs O(n·k) — scan all k elements for every window position. A monotonic deque gets it down to O(n) total.

Keep a deque of indices (not values), maintained so the values they point to are always in decreasing order from front to back. When a new index arrives on the right:

• Pop from the back any indices whose values are smaller than the new one — they can never be the maximum again while a bigger, more recent value sits inside the same window, so there's no reason to keep them.
• Push the new index onto the back.
• Pop from the front whenever that index has slid outside the window's valid range.
• The value at the front of the deque is always the current window's maximum — no scanning required.

Each index is pushed once and popped at most once, so the total work across the entire array is O(n), even though every individual window's maximum is available in O(1). This is the same monotonic-stack idea from the Stacks theory page, just applied at both ends of the structure instead of one.

Open the Sliding Window Maximum visualizer to watch the deque grow and shrink as the window moves.

06 · Complexity

How to reason about time & space

It looks like sliding window should be quadratic — there's a loop for right and, for variable windows, what reads like a nested loop for left. But left and right are each bounded by the array's length, and neither ever moves backward. Across the whole run, right advances at most n times and left advances at most n times — so the combined work is O(n) + O(n) = O(n), not O(n²), despite the nested-looking shape.

Space is whatever running state you need to check validity or track the max: O(k) for a fixed window of size k, O(alphabet size) for a character frequency map (bounded, so effectively constant for most string problems), or O(k) for a monotonic deque that never holds more than the current window's worth of indices.

07 · Before you start coding

Common mistakes

• Forgetting to shrink the window when it becomes invalid — the window silently grows too large and the answer comes out wrong without any obvious error.
• Recalculating the window's contents from scratch on every step — that defeats the entire point; you should be doing O(1) incremental updates, not re-scanning.
• Off-by-one when computing window length: it's right - left + 1, not right - left.
• Moving left by only one step on a repeat instead of jumping straight past the repeated character's last occurrence — this silently reintroduces stale duplicates into the window.
• Scanning a plain array or list inside the window to check "is this valid" instead of maintaining a running count or frequency map — it quietly turns an O(1) check back into O(n) work per step.

08 · Practice

Try it yourself

Both flavors covered above, ready to step through interactively.