Pointers and sliding window · HTML
Maintain summary S for [r-k+1,r]. Add a[r], remove a[r-k] once oversized, and query the summary whenever the window length reaches k.
Recognition signals
- The prompt explicitly says every subarray or substring of length k.
- Contiguity cannot be reordered.
- The window statistic supports incremental addition and removal.
- Naive evaluation recomputes most elements shared by overlapping windows.
False friends
| Signal | Why it is different |
|---|
| Variable-length longest or shortest segment | When validity controls length, use a variable window with repeated shrinking. |
| Any k selected items | A sliding window covers contiguous segments, not combinations. |
Core invariant
After processing right endpoint r, the summary exactly describes the most recent at most k items; a result is recorded only at length k.
State, transition, and processing order
| Item | Definition |
|---|
| State | right, implicit left=right-k+1, aggregate such as sum/frequency/match count, and best result. |
| Transition | Add the new right item, remove the item k positions behind after the prefix is long enough, then read the mature window. |
| Frontier / order | A fixed-width contiguous index segment shifting right by one each round. |
Python skeleton
def max_fixed_sum(values, k):
if k <= 0 or k > len(values):
return None
window = sum(values[:k])
best = window
for right in range(k, len(values)):
window += values[right]
window -= values[right - k]
best = max(best, window)
return best
Correctness sketch
- The initial summary equals the first length-k window.
- Subtracting the sole leaver and adding the sole entrant converts one exact window summary into the next.
- The loop visits every and only length-k window in right-endpoint order, so the recorded optimum is correct.
Complexity
| Time | Space | Parameters |
|---|
| O(n) | O(1) or O(Σ) | n is length; sums need O(1), while frequency state uses Σ distinct keys in the window or domain. |
Edge cases
- For k=1 every singleton is a window.
- For k=n there is one window.
- Define behavior for k≤0 or k>n.
- With negative values, do not initialize the best score to zero.
Error patterns
| Pattern | Why it fails / fix |
|---|
| Off-by-one leaver | A new item at right corresponds to the leaving index right-k. |
| Scoring immature prefixes | The first k-1 prefixes are not length-k windows. |
| Re-summing a slice each round | That regresses to O(nk) and allocates slices. |
Selection and exclusion rules
- Use a fixed window when length is explicitly fixed.
- Prefer incremental state when the statistic supports reversible add/remove.
- For window extrema that are not simply invertible, use a monotonic deque.
Original micro-example
| Part | Detail |
|---|
| Result | The maximum fixed-window sum is 7. |
| Setup | Values [2,5,-1,4], k=2. |
| Trace | Window sums are 7, 4, and 3, each obtained with one add and one subtract. |
Recall prompts
My notes