Sliding Window Median

Share

Given an array nums and integer k, return the median for each sliding window of size k.

Example 1
Input: nums=[1,3,-1,-3,5,3,6,7], k=3 → Output: [1,-1,-1,3,5,6]
Example 2
Input: nums=[1,2,3,4,2,3,1,4,2], k=5 → Output: [2,3,3,3,2]

Solution Approach

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.
Java
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)