480. Sliding Window Median

Leetcode

Neetcode

Intuition

This problem uses the “Two Heaps” approach with a “Lazy Removal” technique:

1. Two Heaps Structure:

   • A max-heap lo to store the smaller half of numbers in the window
   • A min-heap hi to store the larger half of numbers in the window
   • Together, they represent the sorted order of elements

2. Key Properties:

   • For odd-sized windows (k is odd): lo contains (k+1)/2 elements, hi contains (k-1)/2 elements
   • For even-sized windows (k is even): both heaps are balanced with k/2 elements each
   • The median is either the top of lo (when k is odd) or the average of the tops of both heaps (when k is even)

3. Lazy Removal Technique:

   • When an element leaves the window, it’s impractical to remove it from the middle of a heap (not O(1))
   • Instead, we mark it for “delayed removal” in a hash table
   • Only when these “to-be-removed” elements reach the tops of the heaps do we actually remove them
   • This ensures the heap tops always contain valid elements when calculating the median

4. Balance Factor:

   • We maintain a “balance” variable to track how the valid elements should be distributed
   • When an element enters/exits, it can disrupt this balance, so we perform rebalancing operations

The time complexity is O(n·log k) where n is the length of the array and k is the window size.

Java code

class Solution {
    public double[] medianSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        double[] medians = new double[n - k + 1];
        
        // Max heap for smaller half of elements
        PriorityQueue<Integer> lo = new PriorityQueue<>(Collections.reverseOrder());
        // Min heap for larger half of elements
        PriorityQueue<Integer> hi = new PriorityQueue<>();
        // Hash map to track elements to be removed (lazy removal)
        HashMap<Integer, Integer> delayed = new HashMap<>();
        
        // Initialize with first k elements (first window)
        for (int i = 0; i < k; i++) {
            lo.add(nums[i]);
        }
        
        // Balance initial window - move half elements to min heap
        for (int i = 0; i < k/2; i++) {
            hi.add(lo.poll());
        }
        
        // Process all windows
        for (int i = 0; i < n - k + 1; i++) {
            // Calculate median for current window
            medians[i] = k % 2 == 1 ? lo.peek() : ((double)lo.peek() + (double)hi.peek()) * 0.5;
            
            // If last window, no need to process next one
            if (i == n - k) {
                break;
            }
            
            // Current element to remove (leftmost in window)
            int outNum = nums[i];
            // Next element to add (rightmost in next window)
            int inNum = nums[i + k];
            int balance = 0;
            
            // Step 1: Handle outgoing element
            // If outgoing element is in max heap (lo)
            if (!lo.isEmpty() && outNum <= lo.peek()) {
                balance--; // Removing from lo decreases its effective size
            } else {
                balance++; // Removing from hi increases relative size of lo
            }
            // Mark for lazy removal
            delayed.put(outNum, delayed.getOrDefault(outNum, 0) + 1);
            
            // Step 2: Handle incoming element
            // If incoming element belongs in max heap (lo)
            if (!lo.isEmpty() && inNum <= lo.peek()) {
                balance++; // Adding to lo increases its effective size
                lo.add(inNum);
            } else {
                balance--; // Adding to hi decreases relative size of lo
                hi.add(inNum);
            }
            
            // Step 3: Rebalance heaps if needed
            // If lo needs more elements
            if (balance < 0) {
                lo.add(hi.poll());
                balance++;
            }
            // If hi needs more elements
            if (balance > 0) {
                hi.add(lo.poll());
                balance--;
            }
            
            // Step 4: Clean delayed elements from tops of heaps
            // Remove all marked elements from top of lo
            while (!lo.isEmpty() && delayed.getOrDefault(lo.peek(), 0) > 0) {
                int top = lo.poll();
                delayed.put(top, delayed.get(top) - 1);
                if (delayed.get(top) == 0) {
                    delayed.remove(top);
                }
            }
            
            // Remove all marked elements from top of hi
            while (!hi.isEmpty() && delayed.getOrDefault(hi.peek(), 0) > 0) {
                int top = hi.poll();
                delayed.put(top, delayed.get(top) - 1);
                if (delayed.get(top) == 0) {
                    delayed.remove(top);
                }
            }
        }
        
        return medians;
    }
}

Time and Space Complexity Analysis

• Space Complexity: O(k)

  • Two heaps together store at most k elements
  • Hash map for delayed removal can also store at most k elements (in the worst case)

• Time Complexity: O(n·log k)

  • We process n-k+1 windows in total
  • For each window:
    • Computing the median: O(1)
    • Adding elements to heaps: O(log k)
    • Removing elements from heaps: O(log k)
    • Heap balancing operations: O(log k)
  • The lazy removal technique ensures we don’t have to search through the entire heap to remove an element

Implementation Details

1. Initialization:

   • Add first k elements to max heap (lo)
   • Move k/2 elements to min heap (hi) to balance

2. For each window:

   • Calculate current window’s median
   • Mark outgoing element for lazy removal
   • Add incoming element to appropriate heap
   • Rebalance heaps using balance factor
   • Clean tops of heaps by removing marked elements

3. Median calculation:

   • For odd k: median is the top of max heap (lo)
   • For even k: median is average of tops of both heaps

The lazy removal technique is crucial for efficiency since directly removing an element from a heap’s middle would be O(k) time.