In a variable-size sliding window, what decides when the right edge grows versus when the left edge shrinks?
answer
- one pointer moves freely, one moves reluctantly
- growth happens every iteration, unconditionally
- shrinking is triggered only by a violated constraint
- evict from the left until valid again
basics
~10 sThe right edge grows every iteration to admit the next element; the left edge shrinks only when the window's constraint is violated, advancing until the window is valid again. Growth explores; shrinking repairs.
solid answer
~40 sThe scan is asymmetric. The right pointer advances unconditionally, one element per outer iteration, pulling the next element into the window. After each admission you check the window's constraint — say, at most `k` distinct values. If the admission broke the constraint, you advance the left pointer, evicting elements one at a time, exactly until the constraint holds again — not a fixed number of steps. The window is therefore valid again before the next growth step, and its size floats up and down as the data demands. For a longest-valid-window goal, you record the window's size after each repair; the answer is the largest valid window ever observed during the sweep.
go deeper
Be ready to narrate the loop out loud: the right edge moves every step, the left edge moves only to fix a violated constraint. Walking a small example accurately matters more than terminology.
An interviewer expects you to state the invariant — the window is valid at the top of every iteration — and explain why shrinking until valid, rather than by a fixed amount, is what preserves it.
Be ready to map a messy real requirement onto the pattern, notice when the constraint is not window-shaped at all, and name the edge cases — the empty window, a single element violating alone — before writing anything.
Own the framing decision: whether a streaming or log-analysis requirement is genuinely a contiguous-window problem, and steer the team away from force-fitting the pattern where the constraint is not contiguous.
## The shape of the technique A variable-size sliding window maintains a contiguous range `[left..right]` over a sequence and processes the whole sequence in one forward sweep. Unlike a constant-width window, its size is not chosen in advance: the data decides. The loop skeleton is always the same: 1. **Grow:** advance `right` by one and admit the new element into the window's state. 2. **Repair:** while the window violates its constraint, evict the element at `left` and advance `left`. 3. **Record:** update the running answer, now that the window is valid again. The two pointers play different roles. `right` is the explorer — it moves on every single iteration, no exceptions. `left` is the janitor — it moves only when something is wrong, and then only as far as needed to make it right. ## A worked example Suppose you are scanning a captured packet trace for the longest burst of consecutive packets that involves at most `k = 2` distinct source addresses. The sequence of sources is: `A A B A C C B` - Admit `A`, `A`, `B`, `A` — the window `[0..3]` holds 2 distinct sources. Valid; current best length 4. - Admit `C` (index 4) — now 3 distinct sources: violated. Evict from the left: `A`, `A`, `B`, `A` leave one at a time until one source's presence drops to zero. After evicting indices 0–3, the window is `[4..4]` = `C`, back to at most 2 distinct. (A gentler input would have needed only one or two evictions; this one needed four.) - Admit `C`, `B` — window `[4..6]` holds `C C B`, 2 distinct sources, length 3. The answer is 4. Notice what never happened: the window was never rebuilt from scratch, no element was examined more than twice (once entering, once leaving), and `left` never moved backward. ## The invariant The discipline can be stated as a loop invariant: **at the top of every iteration, the window `[left..right]` satisfies the constraint.** Growth may break the invariant; the repair loop restores it before anything else happens. Because the repair loop runs *until* validity returns — rather than evicting some fixed number of elements — the invariant genuinely holds every time you record an answer, which is what makes the recorded lengths meaningful. A second, subtler property: for each position of `right`, the repair loop leaves `left` at the smallest value for which `[left..right]` is valid, i.e. at the *longest* valid window ending at `right`. Since the optimal window ends at some index, it is examined when `right` reaches that index — this is why never revisiting earlier `left` positions loses nothing. ## Why not restart on violation? A tempting alternative is to throw the window away when the constraint breaks and start fresh at the current position. That is both wasteful and wrong: wasteful because elements get rescanned, and wrong because the longest valid run may straddle the violation point — the still-valid suffix of the old window is exactly what the shrink step preserves. ## Two goal directions The grow/shrink skeleton serves two mirrored goals. For a **longest valid window** (constraints like "at most k distinct"), you shrink only while *invalid* and record after repair. For a **shortest window containing something** (constraints like "all required items present"), the direction flips: you grow until the window qualifies, then shrink while it *still* qualifies, recording as you go. Same pointers, opposite shrink condition — mixing the two up is a classic bug. ## Edge cases worth naming aloud - **The empty window.** If a single element by itself violates the constraint (say, a value over a hard cap), the repair loop evicts everything, including that element, leaving `left == right + 1`. Correct code tolerates this; the next growth step recovers naturally. - **No violation ever.** The repair loop simply never runs and the window grows across the entire sequence. - **What "window state" is.** Checking validity usually needs some incrementally maintained summary (counts, a running total). How that bookkeeping works is its own topic; the pattern only requires that admissions and evictions update it consistently.
- Can the left pointer ever pass the right pointer?Yes. If a single element on its own violates the constraint — say a value over a hard cap — the repair loop evicts everything including that element, leaving an empty window with left at right + 1. Correct implementations tolerate the empty window; the next growth step admits the following element and the scan recovers naturally.
- How do you know the optimal window is never missed even though the left edge never moves backward?For each right-edge position, the repair loop stops at the smallest left for which the window is valid — the longest valid window ending there. The optimum ends at some index, so it is examined in full when the right edge reaches that index. Nothing to the left of the final left pointer could extend a valid window, because those starts were already proven invalid with an even shorter span.
- What changes when the goal is the shortest qualifying window instead of the longest valid one?The shrink condition flips. For a shortest-containing goal you grow until the window qualifies, then shrink while it still qualifies, recording candidates during the shrink. For longest-valid you shrink only while invalid and record after the repair. Same two pointers, opposite loop condition — and the correct point to record the answer moves with it.
Like a caterpillar: the head creeps forward every step, and the tail pulls up only when the body has stretched past what it can hold.
saying these in an interview costs you the question
- Moving both pointers together every step, which is a fixed-size window
- Resetting the window to empty whenever the constraint breaks
- Shrinking exactly one element per violation instead of until valid
- Checking validity only once at the end of the scan