DSA problem
Sliding Window Median
The median is the middle value of an ordered list. If the size of the list is even, the median is the average of the two middle values. You are given an integer array nums and an integer k. There is a sliding window of size k that moves from the very left of the array to the very right. You can only see the k numbers in the window. Return the median array for each window in the original input order.
A naive approach sorts every window from scratch, costing O(n * k log k). Inserting and removing one element from a sorted buffer using binary search costs O(log k) for the search but O(k) for the shift, so the total is O(n * k). For large inputs neither is acceptable.
The optimal approach extends the two-heap median trick (low max-heap + high min-heap) with lazy deletion. When the window slides we must conceptually remove the element that just exited, but a binary heap does not support efficient removal of an arbitrary value. Instead we record the value in a "to-delete" hash map and only actually remove it when it bubbles to the top of its heap.
Each step does three things: add the entering element to the appropriate heap, mark the leaving element as pending removal, then rebalance the heap sizes so low has equal or one more live element than high. Before reading the top of either heap, lazily evict any values that are pending removal. Each element is pushed and popped at most once, so the total work is O(n log k).
Examples
nums = [1,3,-1,-3,5,3,6,7], k = 3[1.00000,-1.00000,-1.00000,3.00000,5.00000,6.00000]nums = [1,2,3,4,2,3,1,4,2], k = 3[2.00000,3.00000,3.00000,3.00000,2.00000,3.00000,2.00000]nums = [1,2,3,4], k = 2[1.50000,2.50000,3.50000]Constraints
- 1 <= k <= nums.length <= 10^5
- -2^31 <= nums[i] <= 2^31 - 1
- Answers within 10^-5 of the actual value will be accepted.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.