Sliding Window Median — Two Heaps With Lazy Deletion

Problem Statement

Given an integer array nums and window size k, return the median of every length-k sliding window. For odd k the median is the middle element; for even k it is the average of the two middles.

Constraints:

1 <= k <= nums.length <= 10^5
-2^31 <= nums[i] <= 2^31 - 1
Answers within 1e-5 of the actual value are accepted.

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]

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

Why This Problem Matters

LeetCode 480 — Sliding Window Median — is a Hard that Google, Amazon, and Bloomberg use to test data structure depth. Naive sorting per window is O(n * k log k) and times out. Insertion sort is O(n * k). Only O(n log k) approaches survive at the constraint limits.

The classical answer is two heaps plus lazy deletion. The two heaps maintain median access in O(1); lazy deletion avoids the linear scan a normal heap remove would require. Candidates who hand-roll this cleanly demonstrate fluency with priority queues, heap invariants, and amortised analysis.

This pattern recurs in finance (rolling order statistics), monitoring (rolling p50 latency), and any streaming median problem. Understanding the lazy-deletion trick generalises directly to LeetCode 295, LeetCode 218, and LeetCode 1825.

The Core Insight

Maintain two heaps. lo is a max-heap with the lower half; hi is a min-heap with the upper half. Enforce len(lo) == len(hi) or len(lo) == len(hi) + 1. The median is lo top for odd k, or the average of the two tops for even k.

To slide, push the incoming value into the appropriate heap and rebalance. Mark the outgoing value in a lazy counter map. Before reading a median, prune the tops of both heaps as long as they have pending deletions. This keeps every operation O(log k).

The compute trick for even windows is (-lo.top())/2 + hi.top()/2 instead of (lo.top() + hi.top())/2 to avoid 32-bit overflow when both sides hover near INT_MAX.

Visual Dry Run

nums = [1, 3, -1, -3, 5, 3, 6, 7], k = 3. Showing window snapshots after pruning.

step	window	lo (max)	hi (min)	median
0	1	1	—	not full
1	1,3	1	3	not full
2	1,3,-1	-1,1	3	1.0
3	3,-1,-3	-3,-1	3	-1.0
4	-1,-3,5	-3,-1	5	-1.0
5	-3,5,3	-3,3	5	3.0
6	5,3,6	3,5	6	5.0
7	3,6,7	3,6	7	6.0

Solution (Optimal)

import heapq
from collections import defaultdict
 
class Solution:
    def medianSlidingWindow(self, nums, k):
        # lo: max-heap (negate values), hi: min-heap.
        lo, hi = [], []
        lazy = defaultdict(int)
        res = []
 
        def prune(heap, sign):
            # sign = -1 for lo (values are stored negated), +1 for hi.
            while heap and lazy[sign * heap[0] * -1] > 0:
                actual = sign * heap[0] * -1
                lazy[actual] -= 1
                heapq.heappop(heap)
 
        def rebalance():
            while len(lo) > len(hi) + 1:
                heapq.heappush(hi, -heapq.heappop(lo))
            while len(hi) > len(lo):
                heapq.heappush(lo, -heapq.heappop(hi))
 
        def push(x):
            if lo and x <= -lo[0]:
                heapq.heappush(lo, -x)
            else:
                heapq.heappush(hi, x)
            rebalance()
 
        def median():
            prune(lo, -1)
            prune(hi, 1)
            if k % 2 == 1:
                return float(-lo[0])
            return (-lo[0]) / 2.0 + hi[0] / 2.0
 
        for i, v in enumerate(nums):
            push(v)
            if i >= k:
                out = nums[i - k]
                lazy[out] += 1
                if out <= -lo[0]:
                    prune(lo, -1)
                else:
                    prune(hi, 1)
                rebalance()
            if i >= k - 1:
                res.append(median())
 
        return res

class MinHeap {
    constructor() { this.h = []; }
    size() { return this.h.length; }
    top() { return this.h[0]; }
    push(v) { this.h.push(v); this._up(this.h.length - 1); }
    pop() {
        const t = this.h[0]; const last = this.h.pop();
        if (this.h.length) { this.h[0] = last; this._down(0); }
        return t;
    }
    _up(i) {
        while (i > 0) {
            const p = (i - 1) >> 1;
            if (this.h[p] <= this.h[i]) break;
            [this.h[p], this.h[i]] = [this.h[i], this.h[p]]; i = p;
        }
    }
    _down(i) {
        const n = this.h.length;
        while (true) {
            const l = 2 * i + 1, r = 2 * i + 2; let s = i;
            if (l < n && this.h[l] < this.h[s]) s = l;
            if (r < n && this.h[r] < this.h[s]) s = r;
            if (s === i) break;
            [this.h[s], this.h[i]] = [this.h[i], this.h[s]]; i = s;
        }
    }
}
 
var medianSlidingWindow = function(nums, k) {
    const lo = new MinHeap(), hi = new MinHeap();
    const lazy = new Map();
    const res = [];
    const lc = (x) => lazy.get(x) || 0;
 
    const prune = (heap, sign) => {
        while (heap.size() > 0) {
            const actual = -sign * heap.top();
            if (lc(actual) === 0) break;
            lazy.set(actual, lc(actual) - 1);
            heap.pop();
        }
    };
 
    const rebalance = () => {
        while (lo.size() > hi.size() + 1) hi.push(-lo.pop());
        while (hi.size() > lo.size()) lo.push(-hi.pop());
    };
 
    const push = (x) => {
        if (lo.size() === 0 || x <= -lo.top()) lo.push(-x);
        else hi.push(x);
        rebalance();
    };
 
    const median = () => {
        prune(lo, -1); prune(hi, 1);
        if (k % 2 === 1) return -lo.top();
        return (-lo.top()) / 2 + hi.top() / 2;
    };
 
    for (let i = 0; i < nums.length; i++) {
        push(nums[i]);
        if (i >= k) {
            const out = nums[i - k];
            lazy.set(out, lc(out) + 1);
            if (lo.size() && out <= -lo.top()) prune(lo, -1);
            else prune(hi, 1);
            rebalance();
        }
        if (i >= k - 1) res.push(median());
    }
    return res;
};

Time: O(n log k) — each push, pop, and lazy prune is O(log k). Space: O(k) for the heaps plus the lazy counter.

Common Mistakes

Calling heap.remove(x) directly, which costs O(k) and breaks the time bound.
Rebalancing before pruning, which mistakes stale tops for live elements.
Using (a + b) / 2 for the even median; near INT_MAX the sum overflows, use a/2 + b/2.
Forgetting that values can repeat and using a set instead of a counter for lazy deletions.
Sending large values into lo or small values into hi because the membership check was reversed.

Interview Tips

Sketch the heap invariant on the whiteboard before coding so the interviewer follows.
Explain lazy deletion using "we only clean up when it matters" framing.
Mention SortedList from sortedcontainers as a simpler equivalent if Python is allowed.
Watch out for INT_MAX edge cases and call them out explicitly.

Follow-up Questions

Can SortedList replace the heaps? Yes, with O(log k) insert and delete; simpler but non-stdlib.
What if k = 1? Each median is nums[i] itself; the algorithm still works.
Why is lazy deletion safe? Stale elements never affect the median until they reach the top; pruning before read removes them in time.
How would mode (most frequent) tracking differ? Use a frequency map plus an ordered structure of frequencies.
Maximum lazy map size? Bounded by k because there are at most k deletions in flight.

Key Takeaways

LeetCode 480 is a Hard asked at Google, Amazon, and Bloomberg.
Two heaps maintain the lower and upper halves with O(1) median access.
Lazy deletion defers cleanup until a stale element surfaces at a heap top.
Always prune before reading the median and rebalance after pruning.
For even windows, compute (-lo[0]) / 2 + hi[0] / 2 to avoid overflow.
Total time is O(n log k) with O(k) extra space.
The same template generalises to LeetCode 295, 218, and 1825.

Problem Statement#

Why This Problem Matters#

The Core Insight#

Visual Dry Run#

Solution (Optimal)#

Common Mistakes#

Interview Tips#

Follow-up Questions#

Key Takeaways#

Related reading