Sliding Window And Streaming Statistics

What's being tested

Sliding-window streaming statistics test whether you can maintain aggregates over the last k items without recomputing from scratch. Expect efficient data-structure choices for moving average, minimum/maximum, median, and adjacent array/matrix basics like diagonal checks or BFS path reconstruction.

Patterns & templates

• Fixed-size sliding window — use deque plus running sum; next(x) is O(1) time, O(k) space.

• Moving average — add new value, evict oldest when size exceeds k, return sum / len(window); watch integer overflow.

• Sliding minimum/maximum — use monotonic deque storing indices; each element enters/exits once, so total O(n) time.

• Sliding median — use two heaps: max-heap lower half, min-heap upper half; rebalance sizes after insert/delete.

• Lazy deletion for heaps — maintain delayed[value] counts because arbitrary heap removal is not O(log k) in Python.

• Matrix diagonal / Toeplitz check — verify matrix[r][c] == matrix[r-1][c-1]; O(mn) time, O(1) space.

• 2D pathfinding — use BFS for shortest unweighted path; store parent[(r,c)] to reconstruct path after reaching target.

Common pitfalls

Pitfall: Recomputing sum(window) or sorting each window gives O(nk) or O(nk log k) and usually misses the intended solution.

Pitfall: Median implementations often fail on duplicates unless deletion is counted by value and heap sizes track only valid elements.

Pitfall: Returning average over k before the stream has k elements; usually divide by current window length unless specified otherwise.

Practice these

The practice cards below cover the canonical variants — solve all of them and time yourself.