Given an array nums and integer k, return the median for each sliding window of size k.
Input: nums=[1,3,-1,-3,5,3,6,7], k=3 → Output: [1,-1,-1,3,5,6]Input: nums=[1,2,3,4,2,3,1,4,2], k=5 → Output: [2,3,3,3,2]
Use two heaps (max-heap for lower half, min-heap for upper half) with a lazy deletion map. Balance heaps on each slide.
- Max-heap (lower half) + min-heap (upper half) + HashMap for lazy deletion.
- addNum(x): add to appropriate heap, rebalance.
- removeNum(x): lazy delete (add to map), call rebalance to clean up tops.
- Median = (maxHeap.top + minHeap.top) / 2 or maxHeap.top depending on k parity.
import java.util.*;
class Solution {
public double[] medianSlidingWindow(int[] nums, int k) {
// Two heaps: lo is max-heap (lower), hi is min-heap (upper)
PriorityQueue<Integer> lo = new PriorityQueue<>(Collections.reverseOrder());
PriorityQueue<Integer> hi = new PriorityQueue<>();
Map<Integer,Integer> del = new HashMap<>();
for (int i = 0; i < k; i++) lo.offer(nums[i]);
for (int i = 0; i < k / 2; i++) hi.offer(lo.poll());
double[] res = new double[nums.length - k + 1];
res[0] = k % 2 == 1 ? lo.peek() : ((double)lo.peek() + hi.peek()) / 2;
for (int i = k; i < nums.length; i++) {
int out = nums[i - k], in = nums[i];
int balance = 0;
del.merge(out, 1, Integer::sum);
balance += (out <= lo.peek() ? -1 : 1);
if (in <= lo.peek()) { lo.offer(in); balance++; }
else { hi.offer(in); balance--; }
if (balance > 0) { hi.offer(lo.poll()); }
else if (balance < 0) { lo.offer(hi.poll()); }
while (!lo.isEmpty() && del.getOrDefault(lo.peek(),0) > 0) del.merge(lo.poll(),-1,Integer::sum);
while (!hi.isEmpty() && del.getOrDefault(hi.peek(),0) > 0) del.merge(hi.poll(),-1,Integer::sum);
res[i - k + 1] = k % 2 == 1 ? lo.peek() : ((double)lo.peek() + hi.peek()) / 2;
}
return res;
}
}
- Time Complexity: O(N log K)
- Space Complexity: O(N)