📚 Sliding Window Median – Java Cheat Sheet

📌 What Is It?

The problem involves finding the median of every sliding window of size k in an array. The sliding window moves one step at a time, and the median of the current window is calculated.

To solve this efficiently, we use two heaps:

Max-Heap: Stores the smaller half of the numbers in the current window.
Min-Heap: Stores the larger half of the numbers in the current window.

The heaps are balanced such that the size difference between them is at most 1. This allows us to calculate the median in constant time by looking at the top elements of the heaps.

🧱 Pattern Template

class Solution {
    public double[] medianSlidingWindow(int[] nums, int k) {
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        Map<Integer, Integer> delayed = new HashMap<>(); // Tracks elements to be removed
        double[] result = new double[nums.length - k + 1];
        int left = 0, right = 0;

        while (right < nums.length) {
            // Add the current number to the appropriate heap
            if (maxHeap.isEmpty() || nums[right] <= maxHeap.peek()) {
                maxHeap.offer(nums[right]);
            } else {
                minHeap.offer(nums[right]);
            }

            // Balance the heaps
            balanceHeaps(maxHeap, minHeap);

            // Check if the window size is reached
            if (right - left + 1 == k) {
                // Calculate the median
                if (maxHeap.size() > minHeap.size()) {
                    result[left] = maxHeap.peek();
                } else {
                    result[left] = (maxHeap.peek() + minHeap.peek()) / 2.0;
                }

                // Remove the element going out of the window
                int toRemove = nums[left];
                delayed.put(toRemove, delayed.getOrDefault(toRemove, 0) + 1);
                if (toRemove <= maxHeap.peek()) {
                    maxHeap.poll();
                } else {
                    minHeap.poll();
                }

                // Balance the heaps after removal
                balanceHeaps(maxHeap, minHeap);

                left++; // Slide the window
            }

            right++;
        }

        return result;
    }

    private void balanceHeaps(PriorityQueue<Integer> maxHeap, PriorityQueue<Integer> minHeap) {
        while (maxHeap.size() > minHeap.size() + 1) {
            minHeap.offer(maxHeap.poll());
        }
        while (minHeap.size() > maxHeap.size()) {
            maxHeap.offer(minHeap.poll());
        }
    }
}

📊 Time Complexity

Adding/Removing Elements: O(log k) – Adding or removing elements from a heap takes logarithmic time.
Balancing Heaps: O(log k) – Balancing the heaps after each operation takes logarithmic time.
Overall Complexity: O(n log k) – For an array of size n, each sliding window operation involves logarithmic operations on heaps of size k.

✅ Use Cases

Real-time median calculation in a sliding window
Efficiently handling dynamic datasets
Applications in signal processing and data analysis

📘 Common LeetCode Problems

480. Sliding Window Median [Hard] Two Heaps

🧪 Example: Sliding Window Median

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]

Explanation:
Sliding window size = 3
Window positions and medians:
[1, 3, -1] -> Median = 1.0
[3, -1, -3] -> Median = -1.0
[-1, -3, 5] -> Median = -1.0
[-3, 5, 3] -> Median = 3.0
[5, 3, 6] -> Median = 5.0
[3, 6, 7] -> Median = 6.0

💡 Pro Tips

Use a max-heap for the smaller half and a min-heap for the larger half
Track elements to be removed using a map to avoid unnecessary heap operations
Edge cases: small window size, duplicate elements, negative numbers