Sliding Window Median

480.Sliding Window Median

Sliding Window

Heap

Problem Statement:

Given an array of integers nums and an integer k, find the median of every sliding window of size k. The median is the middle element in an odd-sized list or the average of the two middle elements in an even-sized list.

Algorithm:

1. Use two heaps:
   • maxHeap: stores the smaller half of the elements.
   • minHeap: stores the larger half of the elements.
2. For every element in the array:
   • Add the current element to the appropriate heap.
   • Rebalance the heaps to maintain their size property (difference ≤ 1).
3. After the first k elements:
   • Compute the median and store it in the result.
   • Remove the element leaving the sliding window and rebalance the heaps.
4. Return the result array containing the medians of all sliding windows.

Complexity:

Time: O(n log k), where n is the size of the array and k is the window size | Space: O(k), for storing elements in the heaps.

Java Implementation:

public class Solution {
    // Sliding Window Median using two heaps
    PriorityQueue minHeap = new PriorityQueue<>(); // Min-heap for the larger half
    PriorityQueue maxHeap = new PriorityQueue<>((i1, i2) -> Integer.compare(i2, i1)); // Max-heap for the smaller half

    public double[] medianSlidingWindow(int[] nums, int k) {
        int n = nums.length - k + 1;
        if (n <= 0) return new double[0]; // No windows to process
        double[] result = new double[n];

        for (int i = 0; i <= nums.length; i++) {
            if (i >= k) { // Window is of size k
                result[i - k] = getMedian(); // Store current median
                remove(nums[i - k]); // Remove the element leaving the window
            }
            if (i < nums.length) add(nums[i]); // Add the new element to the window
        }
        return result;
    }

    private void add(int num) {
        // Add the number to the appropriate heap
        if (num < getMedian()) maxHeap.add(num);
        else minHeap.add(num);

        // Rebalance the heaps
        if (maxHeap.size() > minHeap.size()) minHeap.add(maxHeap.poll());
        if (minHeap.size() - maxHeap.size() > 1) maxHeap.add(minHeap.poll());
    }

    private void remove(int num) {
        // Remove the number from the appropriate heap
        if (num < getMedian()) maxHeap.remove(num);
        else minHeap.remove(num);

        // Rebalance the heaps
        if (maxHeap.size() > minHeap.size()) minHeap.add(maxHeap.poll());
        if (minHeap.size() - maxHeap.size() > 1) maxHeap.add(minHeap.poll());
    }

    private double getMedian() {
        // Compute the median based on heap sizes
        if (maxHeap.isEmpty() && minHeap.isEmpty()) return 0;
        if (maxHeap.size() == minHeap.size())
            return ((double) maxHeap.peek() + (double) minHeap.peek()) / 2.0;
        return minHeap.peek();
    }
}
                

Python Implementation:

import heapq

class Solution:
    def medianSlidingWindow(self, nums, k):
        min_heap, max_heap = [], []  # Min-heap and max-heap
        result = []

        def add(num):
            if not max_heap or num <= -max_heap[0]:
                heapq.heappush(max_heap, -num)
            else:
                heapq.heappush(min_heap, num)

            if len(max_heap) > len(min_heap) + 1:
                heapq.heappush(min_heap, -heapq.heappop(max_heap))
            elif len(min_heap) > len(max_heap):
                heapq.heappush(max_heap, -heapq.heappop(min_heap))

        def remove(num):
            if num <= -max_heap[0]:
                max_heap.remove(-num)
                heapq.heapify(max_heap)
            else:
                min_heap.remove(num)
                heapq.heapify(min_heap)

        def get_median():
            if len(max_heap) == len(min_heap):
                return (-max_heap[0] + min_heap[0]) / 2.0
            return -max_heap[0]

        for i in range(len(nums)):
            add(nums[i])
            if i >= k - 1:
                result.append(get_median())
                remove(nums[i - k + 1])

        return result
                

C++ Implementation:

#include 
#include 
#include 

using namespace std;

class Solution {
public:
    vector medianSlidingWindow(vector& nums, int k) {
        priority_queue maxHeap; // Max-heap for the smaller half
        priority_queue, greater> minHeap; // Min-heap for the larger half
        vector result;

        auto add = [&](int num) {
            if (maxHeap.empty() || num <= maxHeap.top())
                maxHeap.push(num);
            else
                minHeap.push(num);

            if (maxHeap.size() > minHeap.size() + 1) {
                minHeap.push(maxHeap.top());
                maxHeap.pop();
            } else if (minHeap.size() > maxHeap.size()) {
                maxHeap.push(minHeap.top());
                minHeap.pop();
            }
        };

        auto remove = [&](int num) {
            if (num <= maxHeap.top())
                maxHeap.remove(num);
            else
                minHeap.remove(num);
        };

        auto getMedian = [&]() -> double {
            if (maxHeap.size() == minHeap.size())
                return ((double) maxHeap.top() + minHeap.top()) / 2.0;
            return maxHeap.top();
        };

        for (int i = 0; i < nums.size(); ++i) {
            add(nums[i]);
            if (i >= k - 1) {
                result.push_back(getMedian());
                remove(nums[i - k + 1]);
            }
        }
        return result;
    }
};