Grow right.
Shrink left.
Never miss.

Sliding window vs two pointers

You've already covered two pointers. The distinction matters more than it looks, so here it is as a crisp two-sentence recap rather than a re-teach.

The fast/slow two-pointer pattern is the mechanical cousin — both pointers move forward only — but fast/slow tracks a write boundary against a uniqueness predicate, not a bounded, property-constrained window. The moment the answer is "a contiguous run satisfying a condition," reach for sliding window.

Derived, not memorized

The canonical entry point is longest substring without repeating characters. Don't jump to the solution — derive it from the brute force and find the redundant work.

The O(n³) brute force

For every pair of indices (i, j), slice out the substring and scan it for duplicates. That's O(n²) pairs, each requiring O(n) duplicate detection — O(n³) total. The obvious O(n²) upgrade: keep a running set as you extend j outward from each fixed i. Cheaper check, same outer loop.

for i from 0 to n - 1:          # fix left edge
    seen = empty set
    for j from i to n - 1:      # extend right edge
        if s[j] in seen: break  # duplicate found, give up
        seen.add(s[j])
        best = max(best, j - i + 1)
# when i advances by 1, we throw away the entire seen set and rebuild from scratch
# that's the waste: everything we learned about the substring starting at i+1

What work is repeated?

When i increments from 0 to 1, the inner loop restarts and re-scans characters starting at index 1 that were already examined. The "window of valid characters" already exists in memory — we just threw it away and rebuilt it. The insight: instead of resetting left and rebuilding, shrink the left edge by one and update the set incrementally.

The core invariant

Every correctly implemented sliding window maintains one invariant. State it explicitly before writing a line of code — the invariant tells you where to record the answer and which direction to shrink:

The corollary: where you record the answer determines which variant you're implementing. For "longest window satisfying property P" — record after the shrink loop, when validity is restored. For "smallest window satisfying P" — record while the window is still valid, inside the shrink loop, before shrinking further. Getting these two placements swapped is the second most common interview bug after the if/while error below.

The shrink-condition trap

This gets disproportionate attention because it's the most reliable source of wrong answers in sliding window problems at Tier-1 interviews — even among candidates who understand the pattern conceptually.

if vs while: when the assumption breaks

Using if to shrink works correctly in exactly one narrow case: when adding a single new element to the right can cause at most one violation, and removing a single element from the left always restores validity in one step. For simple sum-bounded windows with a fixed maximum, this holds. For anything involving frequency maps, distinct character counts, or multiple constraints, it doesn't.

Side-by-side trace: string "abcba", target: longest without repeats

Watch what happens when a second occurrence of 'a' enters the window at right=4. The window is "abcba". Left is at 0.

Note: The trace above is for a string where two characters become duplicated simultaneously. A correct while-loop continues shrinking until all violations are resolved — not just the most recent one. The off-by-one in window length is separate: always use right - left + 1 for inclusive endpoints, not right - left.

Widget A — expand/shrink animator

Step through the window expanding and shrinking on a real string. The frequency map sidebar updates live. Watch the red flash — that's the shrink trigger — and confirm the window is valid before the next expand step begins.

Widget B — fixed vs variable window

Two panels, same underlying array, two problems running in lockstep. Left: a fixed-size-k window sliding mechanically — no shrink, no condition, just slide. Right: a variable window expanding and shrinking for a different problem. The structural difference is what to internalize, not the specific problems.

Widget C — monotonic deque for window maximum

The sliding window maximum problem asks: for each window of size k, what is the maximum element? Naively, scanning the window for a max each time is O(nk). A monotonic deque (double-ended queue) maintains potential maximums in decreasing order, giving O(1) max lookup and O(n) total.

The deque stores indices, not values. Three invariants hold at all times: (1) elements are in decreasing value order front-to-back; (2) the front is always the current window maximum; (3) indices out of the window are evicted from the front.

Two eviction rules, both from different ends:

Pattern recognition: the pre-code checklist

At Tier-1 interviews, the problem won't announce "use sliding window." Here's what to listen for, especially in stacked-constraint framing where the technique isn't obvious:

Sliding window in real systems

The sliding window pattern appears across systems engineering in three specific forms that are worth naming, because encountering them in production code without recognizing the interview pattern is a missed connection.

TCP congestion window. TCP's congestion control maintains a "window" of bytes that can be in-flight at once — sent but not yet acknowledged. The window grows when acknowledgments arrive (expand right) and shrinks on detected loss (shrink left). The invariant is identical to the interview problem: the window bounds a contiguous, valid, dynamically-resized range, and boundary movement is event-driven rather than clock-driven.

Streaming record validation. A streaming record validator that must never hold an entire dataset in memory is a direct real-world cousin of the fixed-size sliding window: rolling validity checks over "the last N records" — rate-of-violation-in-the-last-1000-records monitoring, for instance — use exactly the expand-and-evict discipline of a fixed-size window, where evicting the oldest record as a new one arrives is structurally the same as advancing the left pointer. The same amortized-O(n) argument applies: each record enters and leaves the window exactly once.

Statistical drift detection. Engineers building drift-detection tooling that bins a data stream into quantile buckets in a single pass are applying the same "maintain a running, bounded-memory summary as data flows past once" discipline that makes sliding window O(n) instead of O(n²). The amortized-pointer-movement argument from the interview technique is the same argument that justifies why a streaming statistics pass doesn't need to revisit old data — each data point contributes to the running summary once, then leaves the active window.

Problem set — 10

Ordered easy to hard. Fixed window first, then variable, then stacked-constraint and reframing problems. Four are explicitly marked for Widget A or C re-use — same visual vocabulary, different parameters, faster pattern recognition.

Pseudocode templates

Three templates. Every annotation is a trap you will encounter, not a formality.

function fixed_window(arr, k):
    n = length(arr)
    if n < k: return NONE          # guard: array smaller than window

    window_val = aggregate(arr[0 .. k-1])  # seed the first window
    best = window_val

    for right from k to n - 1:
        # slide: add incoming element, remove outgoing element
        window_val = update(window_val, add=arr[right], remove=arr[right - k])
        best = max(best, window_val)

    return best
    # note: no shrink loop, no condition check — just slide by one each step
    # window size is always exactly k; right - left + 1 = k at all times

function variable_window_max(arr, condition):
    left = 0
    best = 0
    # initialize any window state: freq map, running sum, distinct count, etc.
    state = empty

    for right from 0 to n - 1:

        # ① EXPAND: unconditionally add arr[right] to state
        state.add(arr[right])

        # ② SHRINK: restore validity — use WHILE, never IF
        while NOT valid(state):          # ← WHILE, never if
            state.remove(arr[left])
            left = left + 1

        # ③ RECORD: window is now valid — record the best
        # placement here (AFTER while) is for maximize problems
        best = max(best, right - left + 1)    # ← +1 for inclusive

    return best

# for MINIMIZE problems: record INSIDE the while loop before shrinking
function variable_window_min(arr, condition):
    left = 0
    best = INFINITY
    state = empty

    for right from 0 to n - 1:
        state.add(arr[right])

        while valid(state):                 # shrink WHILE still valid (opposite!)
            best = min(best, right - left + 1)  # ← record BEFORE shrinking
            state.remove(arr[left])
            left = left + 1

    return best if best != INFINITY else -1

function window_max(arr, k):
    n = length(arr)
    dq = empty deque                    # stores indices, values are decreasing
    output = []

    for right from 0 to n - 1:

        # STEP 1: evict from back — remove dominated elements
        while dq not empty AND arr[dq.back()] <= arr[right]:
            dq.pop_back()               # smaller/equal elements can never win
        dq.push_back(right)

        # STEP 2: evict from front — remove out-of-window indices
        if dq.front() < right - k + 1:
            dq.pop_front()              # index slid out of the window

        # STEP 3: output max once window is full
        if right >= k - 1:
            output.append(arr[dq.front()])  # front is always current max

    return output
    # note: "less than" vs "less than or equal" in step 1 matters when values tie
    # using <= means equal elements at the back are evicted — the newer one is kept
    # this is correct: an older equal element would leave the window sooner

Further reading