Sliding Window Median — Two Heaps with Lazy Deletion

Problem Statement#

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

Constraints:

• 1 <= k <= nums.length <= 10^5
• -2^31 <= nums[i] <= 2^31 - 1

Input:  nums = [1,3,-1,-3,5,3,6,7], k = 3
Output: [1, -1, -1, 3, 5, 6]

Input:  nums = [1,2,3,4,2,3,1,4,2], k = 3
Output: [2, 3, 3, 3, 2, 3, 2]

Why This Problem Matters#

This is the harder cousin of LeetCode 295 (Find Median from Data Stream). Bloomberg, Google, and quant trading firms love this priority queue interview question because it merges two patterns: two-heap median maintenance and sliding window with deletes.

The challenge is that standard heaps do not support arbitrary remove in O(log n). A naive linear scan blows the time budget at 10^5 elements. The fix — lazy deletion via a hash map — is a heap FAANG technique worth memorizing.

The Core Insight#

Maintain a max-heap of the lower half and a min-heap of the upper half, just like classic median. When the window slides, mark the outgoing element for lazy deletion in a counter dictionary. Whenever the heap top is in the delete map, pop it and decrement the counter.

This keeps all operations amortized O(log k) and the active heap size always equals k.

Visual Dry Run#

For nums = [1,3,-1,-3,5], k = 3:

Solution (Optimal)#

import heapq
from collections import defaultdict
 
class Solution:
    def medianSlidingWindow(self, nums, k):
        low, high = [], []
        delayed = defaultdict(int)
        balance = 0
        res = []
 
        def prune(heap):
            while heap:
                top = -heap[0] if heap is low else heap[0]
                if delayed[top] > 0:
                    delayed[top] -= 1
                    heapq.heappop(heap)
                else:
                    break
 
        for i, num in enumerate(nums):
            if not low or num <= -low[0]:
                heapq.heappush(low, -num)
                balance += 1
            else:
                heapq.heappush(high, num)
                balance -= 1
 
            if i >= k:
                out = nums[i - k]
                delayed[out] += 1
                balance += -1 if out <= -low[0] else 1
 
            if balance > 1:
                heapq.heappush(high, -heapq.heappop(low))
                balance -= 2
            elif balance < 0:
                heapq.heappush(low, -heapq.heappop(high))
                balance += 2
 
            prune(low); prune(high)
 
            if i >= k - 1:
                if k % 2:
                    res.append(float(-low[0]))
                else:
                    res.append((-low[0] + high[0]) / 2.0)
        return res

var medianSlidingWindow = function(nums, k) {
    const low = new MaxHeap();
    const high = new MinHeap();
    const delayed = new Map();
    let balance = 0;
    const res = [];
 
    const prune = heap => {
        while (heap.size() && (delayed.get(heap.top()) || 0) > 0) {
            delayed.set(heap.top(), delayed.get(heap.top()) - 1);
            heap.pop();
        }
    };
 
    for (let i = 0; i < nums.length; i++) {
        if (!low.size() || nums[i] <= low.top()) { low.push(nums[i]); balance++; }
        else { high.push(nums[i]); balance--; }
 
        if (i >= k) {
            const out = nums[i - k];
            delayed.set(out, (delayed.get(out) || 0) + 1);
            balance += out <= low.top() ? -1 : 1;
        }
        if (balance > 1) { high.push(low.pop()); balance -= 2; }
        else if (balance < 0) { low.push(high.pop()); balance += 2; }
        prune(low); prune(high);
 
        if (i >= k - 1) {
            res.push(k % 2 ? low.top() : (low.top() + high.top()) / 2);
        }
    }
    return res;
};

Time: O(n log k) — each push and prune costs log k; lazy deletes amortize to log k. Space: O(k) — the active heaps plus a bounded delayed map.

Common Mistakes#

• Trying to actually remove an element from the middle of a heap (O(n))
• Forgetting to prune both heaps after rebalancing
• Mismanaging the balance counter when the outgoing element is on the high side
• Integer overflow on the median average — cast to float or use BigInt
• Forgetting that the prune step must run before reading heap tops

Interview Tips#

• Explain lazy deletion before writing code — it is the differentiator
• Track a balance counter rather than using raw heap sizes because lazy entries skew counts
• Test with k = 1 (median is the element), k = n (single window)
• Mention that a sorted multiset is an alternative, but Python lacks one in the stdlib

Follow-up Questions#

• What if k can change between queries? Use an indexed sorted container instead
• What if updates can edit any past index? Move to a balanced BST
• Can you do it with one balanced BST? Yes, using order statistics — O(n log k)
• What is the memory cost of the delayed map in the worst case? Bounded by n, but practically by the window size
• How would you parallelize across many windows? Compute on disjoint chunks and merge

Key Takeaways#

• Sliding-window median needs lazy deletion because heaps cannot remove arbitrary keys
• Maintain a balance counter — do not trust raw heap sizes after lazy deletes
• Always prune the heap top before reading the median
• O(n log k) time, O(k) space
• This is the canonical extension of two-heap median for sliding windows
• The same lazy-deletion trick works for top-k frequency in a stream
• Memorize this as a Bloomberg and Google priority queue interview classic