For each window of k consecutive elements, from left to right, return the median of the window. For even k, the median is the mean of the two middle values.
Before you code
Each step adds one value and removes another. Which structures can remove an arbitrary value and still report the middle quickly?
Hints
- With an ordered multiset such as SortedList: add the new value, remove the leaving one, and read the middle by index. O(n log k).
- With two heaps: keep the lower half in a max-heap and the upper half in a min-heap. Removing an arbitrary value is the hard part: record it in a "to delete" counter and discard it only when it reaches the top of its heap.
- With lazy deletion, keep track of each heap's real size separately from its length, and rebalance using the real sizes.
Production & complexity notes
When solving Sliding window median on LeetCode (hard), always state your loop or recursion invariant before writing code. Verify how your chosen data structure behaves on degenerate inputs (single-element inputs, all-duplicate keys, strictly monotonic sequences, or maximum constraint sizes up to $10^5$ elements). In production interviews, pair your implementation with an explicit time and auxiliary space complexity proof, explain why alternative brute-force approaches violate the latency budget, and trace how cache locality and memory allocation overhead affect wall-clock throughput on real hardware. Review the step-by-step memory trace in Choosing an ordered structure to reinforce the underlying pattern.
What it practices
Choosing between an ordered set and heaps, from Choosing an ordered structure.