Recognizing a sliding-window problem
“How do you recognize that a problem calls for a sliding window, and when does the pattern fail?”
What this tests
- Whether the candidate can articulate the invariant that makes a window valid.
- Understanding that the pattern requires monotonicity of the constraint as the window grows and shrinks.
- Ability to distinguish fixed-size, variable-size and frequency-based windows.
- Knowledge of the failure case (negatives, non-monotone constraints) and the alternative.
Strong answer
The signals are: contiguous subarray or substring, an optimization or count over it ("longest", "shortest", "number of"), and a constraint that can be maintained incrementally as elements enter and leave. If adding an element only makes the constraint harder to satisfy and removing one only makes it easier, the window can expand right and shrink left with two pointers, each moving n times at most — O(n) total.
Three flavours. Sliding Window (Fixed Size): the size k is given, maintain a running aggregate. Sliding Window (Variable Size): expand until invalid, shrink until valid again, record the best. Sliding Window with Frequency Map: the constraint is over character counts ("at most k distinct", "anagram of p"), so a count map or array tracks validity in O(1) per step.
The pattern fails when the constraint is not monotone in the window. Subarray sum equals k with negative numbers is the classic trap: growing the window can decrease the sum, so shrinking is no longer a valid response. That problem moves to Prefix Sum with a hash map. Similarly, "maximum in each window" needs a Monotonic Queue rather than a plain aggregate, because the maximum cannot be updated in O(1) when the old max leaves.
A strong candidate states the invariant explicitly before coding ("the window [l, r] always satisfies constraint C after the shrink loop") and uses it to justify why the answer is recorded at the right moment.
Green flags · Red flags
- Says "contiguous" and "monotone constraint" as the two requirements.
- Identifies negative numbers as the reason sum-based windows break and names prefix sums as the fix.
- Explains the
O(n)bound via each pointer moving at mostntimes. - States the window invariant explicitly.
- Knows the difference between "at most
k" (direct) and "exactlyk" (difference of two at-most counts).
- Applies a sliding window to a subsequence problem.
- Cannot say why the algorithm is
O(n)rather thanO(n^2). - Uses a window for subarray sum
= kwith negative values. - Shrinks the window with an
ifinstead of awhilewhen multiple removals may be needed.
Follow-up questions
Each follow-up changes a requirement; the right answer changes with it.
k distinct elements.t.