Patterns / Sliding Window

Sliding Window Pattern

Grow the window on the right; shrink it from the left only when it breaks a rule. Every element enters and leaves at most once.

What it is

A sliding window maintains a contiguous range over an array or string and an invariant about its contents (at most k distinct characters, no repeats, sum below a limit). You expand the right edge to include new elements, and when the invariant is violated you advance the left edge until it holds again. Because both edges only move forward, the total work is linear — far better than re-scanning every sub-range.

When to use it — the signals

"Longest/shortest substring or subarray such that…".
A constraint on what the window may contain (≤ k distinct, sum ≤ S, all unique).
"Maximum/minimum over every window of fixed size k".

How it works

A representative implementation in Java:

// Longest substring without repeating characters.
Set<Character> window = new HashSet<>();
int left = 0, best = 0;
for (int right = 0; right < s.length(); right++) {
    while (window.contains(s.charAt(right))) {
        window.remove(s.charAt(left++));   // shrink until valid
    }
    window.add(s.charAt(right));
    best = Math.max(best, right - left + 1);
}
return best;

Complexity

O(n) — each index is added and removed from the window at most once. Space is O(k) for the window contents.

Common pitfalls

Shrinking with an if when a while is needed (the invariant can break by more than one).
Updating the answer at the wrong moment (before vs after restoring validity).
Confusing fixed-size and variable-size window logic.

Practice problems

Classic problems where this pattern is the intended approach: Longest Substring Without Repeating Characters, Minimum Size Subarray Sum, Permutation in String, Sliding Window Maximum. Work through them on the Leet Study home page.

← All patterns