When to use it#
Look for the structural evidence below before naming the pattern. The constraints and invariant - not a keyword - make the choice defensible.
Recognition signals
- Longest, shortest, or count of contiguous ranges
- Incremental add/remove state
When another approach fits better
- The property is not maintainable when an item leaves
- The chosen validity condition is non-monotonic as the left boundary advances
How it works#
Enumerate all O(n²) ranges and recompute each range property from scratch.
Express the range property as incrementally addable/removable state.
Grow the right edge once per element.
Shrink with while - not a single if - until the invariant is restored, then score the window.
InvariantAfter the repair loop, the active window satisfies the declared condition and its maintained state equals exactly its contents.
Example and template#
Longest Substring Without Repeating Characters
Maintain the smallest valid left boundary as characters repeat.
Open the full problem brief- Grow
[A B C A]The repeated A violates uniqueness.
- Repair
A [B C A]Advance left until the duplicate leaves; the window is valid again.
left = 0
state = empty
for right in 0..n-1:
add input[right] to state
while window is invalid:
remove input[left] from state
left += 1
update answer from [left, right]- Time
- O(n)
- Space
- O(k)
- Assumptions
- Each boundary advances at most n times and state updates are O(1) expected; k is retained state size.
Pitfalls#
Common wrong approaches
One removal may not restore validity, leaving the scoring step on an invalid window.
A fixed-width window evicts by size; a variable window repairs a predicate.
Edge cases
- Empty input
- A window of length one
- No valid nonempty range
- Count entries reaching zero
Interview narration
- “I can update this contiguous range in constant time at either edge.”
- “Right explores; left only moves to restore the constraint.”
- “Once valid, this is the best candidate ending at right under this objective.”
Practice#
Longest Substring Without Repeating Characters
Maintain the smallest valid left boundary as characters repeat.
Practice this problemFind the smallest contiguous batch whose total reaches a positive threshold.
Reveal the pattern decision
A variable window works only because positive values make removing from the left change feasibility monotonically.
Transfer problem
Find the longest interval with at most two event categories after normalizing aliases.
Checkpoint: Maintain normalized category counts and delete zero-count keys during repair.
Follow-up variations
- Return the range boundaries, not only its size
- Explain why negative values invalidate the positive-sum window proof
Error-log prompts
- Did state equal exactly the active window?
- Why was the repair condition monotonic?