Pointers and sliding window · HTML
Add each right endpoint once. While invalid for a longest-valid task, or while valid for a shortest-cover task, move left and remove its contribution. Both pointers are monotone.
Recognition signals
- The answer must be a contiguous subarray or substring.
- Frequency, kind count, or nonnegative sum supports incremental maintenance.
- Right expansion affects validity in one direction and left contraction restores or tightens it.
- The objective is a longest valid or shortest covering interval.
False friends
| Signal | Why it is different |
|---|
| Sum constraint with arbitrary negatives | Expanding can lower the sum and shrinking can raise it, destroying pointer monotonicity; use prefix state or a monotonic deque. |
| Noncontiguous subsequence | A window cannot skip intervening items. |
Core invariant
left and right never retreat; whenever a result is recorded, the maintained state exactly matches [left,right] and satisfies the variant's validity or minimality condition.
State, transition, and processing order
| Item | Definition |
|---|
| State | left, right, window frequency/sum/missing count, and best; define symmetric add and remove operations. |
| Transition | Add right, repeatedly remove left according to the objective until validity is restored or further contraction would break coverage, and update at the proper moment. |
| Frontier / order | Among all windows ending at current right, monotonicity compresses candidates to one critical left boundary. |
Python skeleton
def longest_at_most_k_distinct(values, k):
if k < 0:
return 0
count, left, best = {}, 0, 0
for right, value in enumerate(values):
count[value] = count.get(value, 0) + 1
while len(count) > k:
old = values[left]
count[old] -= 1
if count[old] == 0:
del count[old]
left += 1
best = max(best, right - left + 1)
return best
Correctness sketch
- Symmetric add/remove keeps the frequency state equal to the actual interval.
- When distinct>k, every window with a smaller left is also invalid, so contraction discards no valid optimum.
- After validity returns, left is the farthest-left valid boundary for this right, so its length represents the best candidate ending here.
Complexity
| Time | Space | Parameters |
|---|
| O(n) | O(Σ) | Each item enters once through right and leaves at most once through left; Σ is the number of distinct active keys. |
Edge cases
- Empty input returns zero or the documented no-window value.
- For k=0, only an empty window is valid.
- Delete a frequency key at zero or distinct count remains wrong.
- A shortest-cover variant updates inside its contraction loop, unlike longest-valid.
Error patterns
| Pattern | Why it fails / fix |
|---|
| Using if instead of while | One left move may not restore validity; contraction must continue. |
| Forcing every interval problem into a window | Prove pointer monotonicity first, especially with negative values or nonmonotone predicates. |
| Updating at the wrong time | Longest-valid records after restoration; shortest-cover usually records while still covered and shrinking. |
Selection and exclusion rules
- Use a window for contiguous state with incremental updates and a monotone left restoration rule.
- For longest valid, shrink on violation and record after validity.
- For shortest covering, record and shrink while covered until coverage breaks.
Original micro-example
| Part | Detail |
|---|
| Result | The longest valid window has length 3. |
| Setup | Sequence [a,b,a,c,c], allowing at most 2 distinct values. |
| Trace | On c, window a,b,a,c has 3 kinds, so left advances until b disappears; later c,c can extend. |
Recall prompts
My notes