Sliding Window Median with Lazy Deletion — The Ultimate Two-Heap Template

Problem Statement#

Given an integer array nums and an integer k, there is a sliding window of size k which is moving from the left to the right of the array. Each time the sliding window moves right by one position, find the median of the k numbers in the window.

The median is the middle value in a sorted list. For even k, the median is the average of the two middle values.

Constraints:

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

Examples:

Example 1:
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]
 
Example 2:
Input: nums = [1,2,3,4,2,3,1,4,2], k = 5
Output: [2.0,3.0,3.0,3.0,2.0]

Why This Problem Matters#

Sliding Window Median is arguably the hardest pure heap problem in the LeetCode canon. Google, Amazon, and Microsoft use it in senior engineering roles because it demands mastery of three concepts simultaneously: two-heap median tracking, lazy deletion, and sliding window management.

The problem is a critical benchmark for understanding lazy deletion heaps — a technique where you mark elements as "deleted" rather than removing them immediately, pruning lazily when the target element floats to the top. This pattern is essential when you need to efficiently remove arbitrary elements from a heap (not just the top), which standard heap operations don't support directly.

In production systems, this pattern appears in streaming analytics platforms (compute rolling median of sensor readings), financial systems (rolling median bid-ask spreads), and monitoring dashboards. Elasticsearch, for example, uses a variant of this algorithm for percentile aggregations over time windows.

Once you understand the lazy deletion two-heap template here, you can apply it to any problem requiring a dynamic sorted window: "Find Median from Data Stream" becomes a special case, "Design a Leaderboard" becomes manageable, and "Sliding Window Quartile" is a direct extension.

The Core Insight#

Two-heap invariant: Maintain a max-heap lo (lower half) and a min-heap hi (upper half) such that:

• Every element in lo ≤ every element in hi.
• |lo_size - hi_size| <= 1.
• Median = top of lo (if sizes equal or lo has one more).

Adding an element: Push to lo. If top of lo > top of hi, swap the tops. Rebalance sizes.

Removing an element (the hard part): You can't remove from the middle of a heap in O(log n). Instead, use lazy deletion:

• Mark the element as "to be deleted" in a hash map counter.
• Adjust the logical sizes (lo_size, hi_size) without touching the heap.
• When computing the median, prune the top of each heap by skipping elements marked for deletion.

Sliding window: For window [i, i+k-1], on each slide:

1. Add nums[i+k-1].
2. Remove nums[i-1] (lazy deletion).
3. Rebalance.
4. Compute median.

Visual Dry Run#

nums = [1, 3, -1, -3, 5, 3, 6, 7], k = 3
 
Window [1,3,-1]:
  Add 1 → lo=[1], hi=[]. Add 3 → lo=[1], hi=[3]. Add -1 → lo=[-1,1], hi=[3].
  Balanced: lo=[-1,1], hi=[3]. lo_top=1. Median = 1.0. ✓
 
Window [3,-1,-3]:
  Add -3. lo=[−3,−1,1], hi=[3]. Over-balanced: move 1 to hi.
  lo=[−3,−1], hi=[1,3]. lo_top=−1. Median = −1.0.
  Remove 1 (going out). 1 is in hi. hi_size−=1. lo=[−3,−1], hi=[3]. Balanced.
  Median: lo_size=2, hi_size=1. lo_top=−1. → −1.0. ✓
 
Window [-1,-3,5]:
  Add 5: hi=[3,5]. Remove 3 (going out). hi_size−=1. Check lazy.
  lo=[−3,−1], hi=[5]. Balanced: lo=2, hi=1.
  Median = lo_top = −1. ✓  (Actual sorted: [−3,−1,5] → median=−1) ✓
  
... continue similarly ...

Solution (Optimal)#

import heapq
from collections import defaultdict
 
def medianSlidingWindow(nums, k):
    lo = []   # max-heap (negated), stores lower half
    hi = []   # min-heap, stores upper half
    lo_size = hi_size = 0
    trash = defaultdict(int)  # lazy deletion counter
    
    def add(num):
        nonlocal lo_size, hi_size
        if not lo or num <= -lo[0]:
            heapq.heappush(lo, -num)
            lo_size += 1
        else:
            heapq.heappush(hi, num)
            hi_size += 1
        rebalance()
    
    def remove(num):
        nonlocal lo_size, hi_size
        trash[num] += 1
        if num <= -lo[0]:
            lo_size -= 1
        else:
            hi_size -= 1
        rebalance()
    
    def rebalance():
        nonlocal lo_size, hi_size
        # lo should have exactly (k+1)//2 live elements, hi has k//2
        while lo_size > hi_size + 1:
            prune(lo)
            val = -heapq.heappop(lo)
            lo_size -= 1
            heapq.heappush(hi, val)
            hi_size += 1
            prune(hi)
        while hi_size > lo_size:
            prune(hi)
            val = heapq.heappop(hi)
            hi_size -= 1
            heapq.heappush(lo, -val)
            lo_size += 1
            prune(lo)
    
    def prune(heap):
        # Remove lazily deleted elements from the top
        while heap:
            top = abs(heap[0])
            if trash[top] > 0:
                trash[top] -= 1
                heapq.heappop(heap)
            else:
                break
    
    def get_median():
        prune(lo)
        prune(hi)
        if k % 2 == 1:
            return float(-lo[0])
        return (-lo[0] + hi[0]) / 2.0
    
    result = []
    
    # Initialize first window
    for i in range(k):
        add(nums[i])
    result.append(get_median())
    
    # Slide the window
    for i in range(k, len(nums)):
        add(nums[i])
        remove(nums[i - k])
        result.append(get_median())
    
    return result

function medianSlidingWindow(nums, k) {
    // In JS, simulate with two sorted arrays (lo descending, hi ascending)
    // For full correctness with large inputs, use a proper heap library
    const lo = [];  // max-heap (sorted descending)
    const hi = [];  // min-heap (sorted ascending)
    const trash = new Map();
    let loSize = 0, hiSize = 0;
    
    const sortedInsert = (arr, val, desc) => {
        let lo2 = 0, hi2 = arr.length;
        while (lo2 < hi2) {
            const mid = (lo2 + hi2) >> 1;
            if (desc ? arr[mid] > val : arr[mid] < val) lo2 = mid + 1;
            else hi2 = mid;
        }
        arr.splice(lo2, 0, val);
    };
    
    const prune = (arr, desc) => {
        while (arr.length) {
            const top = arr[0];
            if ((trash.get(top) || 0) > 0) {
                trash.set(top, trash.get(top) - 1);
                arr.shift();
            } else break;
        }
    };
    
    const getMedian = () => {
        prune(lo, true); prune(hi, false);
        if (k % 2 === 1) return lo[0];
        return (lo[0] + hi[0]) / 2;
    };
    
    const add = (num) => {
        if (!lo.length || num >= lo[0]) { sortedInsert(hi, num, false); hiSize++; }
        else { sortedInsert(lo, num, true); loSize++; }
        // Rebalance: lo should have Math.ceil(k/2) elements
        while (loSize < hiSize) { prune(hi, false); sortedInsert(lo, hi.shift(), true); loSize++; hiSize--; }
        while (loSize > hiSize + 1) { prune(lo, true); sortedInsert(hi, lo.shift(), false); hiSize++; loSize--; }
    };
    
    const remove = (num) => {
        trash.set(num, (trash.get(num) || 0) + 1);
        if (lo.length && num <= lo[0]) loSize--;
        else hiSize--;
        while (loSize < hiSize) { prune(hi, false); sortedInsert(lo, hi.shift(), true); loSize++; hiSize--; }
        while (loSize > hiSize + 1) { prune(lo, true); sortedInsert(hi, lo.shift(), false); hiSize++; loSize--; }
    };
    
    const result = [];
    for (let i = 0; i < k; i++) add(nums[i]);
    result.push(getMedian());
    for (let i = k; i < nums.length; i++) {
        add(nums[i]);
        remove(nums[i - k]);
        result.push(getMedian());
    }
    return result;
}

Complexity Analysis:

• Time: O(n log k) amortized — each element is added and removed once; each heap operation is O(log k); lazy deletion is amortized O(1)
• Space: O(k + n) — heaps hold k live elements plus at most n lazily deleted elements

Common Mistakes#

• Tracking heap physical size instead of logical size. After lazy deletion, the heap contains deleted elements. Always track live sizes separately (lo_size, hi_size) and use those for balance checks and median computation.
• Pruning in the wrong order. Prune before accessing the top of the heap. If you access heap[0] before pruning, you might read a deleted element.
• Rebalancing based on the wrong target. For window size k: lo should have ceil(k/2) live elements, hi should have floor(k/2). Or equivalently, lo has at most 1 more than hi.
• Integer overflow in median computation. For even k, (-lo[0] + hi[0]) / 2.0 — both values can be large. Ensure you use 64-bit arithmetic.
• Forgetting that Python's heapq stores min-heap. For lo (lower half as max-heap), negate all values before pushing.

Follow-up Questions#

1. What is the amortized cost per prune operation? (Hint: Each element is pruned at most once after being added to the trash.)
2. Can you implement this without lazy deletion? (Hint: Use a sorted set/TreeMap with a manual median tracker.)
3. Extend to percentile windows: Instead of median (50th percentile), compute the 25th or 75th percentile.
4. What if elements can be duplicated? Does the lazy deletion logic still work correctly?
5. For very large k (k ≈ n), is the heap approach still optimal? What alternatives exist?

Key Takeaways#

• Sliding Window Median requires two heaps (max-heap lo, min-heap hi) plus lazy deletion to handle arbitrary removals in O(log k) amortized per operation.
• Track logical sizes (lo_size, hi_size) separately from physical heap size — deleted elements remain in the heap until they float to the top.
• Rebalance after every add and remove: lo holds ceil(k/2) live elements; median = lo[0] for odd k or average of both tops for even k.
• Prune lazily: only skip deleted elements when they reach the top — each element is pruned at most once, giving O(1) amortized cost.
• Time is O(n log k) amortized; space is O(k + n) since the heap can accumulate up to n lazily deleted entries.
• The lazy deletion two-heap template appears in LeetCode 218 (Skyline Problem) — any problem requiring removal from an arbitrary heap position.
• Google and Microsoft use this to test advanced heap mastery; mention the lazy deletion technique by name in interviews.