Find medians of all windows of size k in array nums.
Input: nums=[1,3,-1,-3,5,3,6,7], k=3 → Output: [1.0,-1.0,-1.0,3.0,5.0,6.0]
Input: nums=[1,2,3,4,2,3,1,4,2], k=3 → Output: [2.0,3.0,3.0,3.0,2.0,3.0,2.0]
Two heaps (max for lower half, min for upper half) with lazy deletion for elements leaving window.
- Max-heap lo, min-heap hi balanced such that |lo|-|hi| <= 1
- Add element, balance heaps
- For outgoing element: add to "trash" set (lazy delete)
- Balance heaps accounting for lazy deleted items
- Median = lo.top() or (lo.top()+hi.top())/2
public double[] medianSlidingWindow(int[] nums, int k) {
PriorityQueue<Integer> lo = new PriorityQueue<>(Collections.reverseOrder());
PriorityQueue<Integer> hi = new PriorityQueue<>();
Map<Integer, Integer> trash = new HashMap<>();
for (int i = 0; i < k; i++) { lo.add(nums[i]); }
for (int i = 0; i < k / 2; i++) hi.add(lo.poll());
double[] res = new double[nums.length - k + 1];
for (int i = k; ; i++) {
res[i - k] = (k % 2 == 1) ? lo.peek() : ((double)lo.peek() + hi.peek()) / 2;
if (i == nums.length) break;
int out = nums[i - k], in = nums[i];
int balance = 0;
balance += (out <= lo.peek()) ? -1 : 1;
trash.merge(out, 1, Integer::sum);
if (in <= lo.peek()) { lo.add(in); balance++; } else { hi.add(in); balance--; }
if (balance > 0) { hi.add(lo.poll()); }
else if (balance < 0) { lo.add(hi.poll()); }
while (!lo.isEmpty() && trash.getOrDefault(lo.peek(),0) > 0) { trash.merge(lo.peek(),-1,Integer::sum); lo.poll(); }
while (!hi.isEmpty() && trash.getOrDefault(hi.peek(),0) > 0) { trash.merge(hi.peek(),-1,Integer::sum); hi.poll(); }
}
return res;
}
- Time Complexity: O(n log k)
- Space Complexity: O(k)