Leetcode 480. Sliding Window Median

Let's understand what we're being asked to do. We have an array like [1, 3, -1, -3, 5, 3, 6, 7] and a window size k=3. We need to slide a window of size 3 across the array and find the median of each window.

Tracing through: Window [1, 3, -1] has median 1 (middle value when sorted). Window [3, -1, -3] has median -1. Window [-1, -3, 5] has median -1. And so on.

Important constraint: For even k, the median is the average of the two middle values. For odd k, it's the single middle value. The array can have up to 1e5 elements, so we need an efficient solution.

Edge cases to consider: What if k=1 (every element is its own median)? What if the array has negative numbers? What if k equals the array length (only one window)?

The straightforward approach is to extract each window of size k, sort it, and find the median. For each of the n-k+1 windows, we create a copy of k elements, sort them in O(k log k) time, and pick the middle element(s). This is simple to implement but inefficient because we're re-sorting mostly the same elements repeatedly.

As the window slides right by one position, we remove one element from the left and add one element to the right. The median changes, but most elements in the window stay the same.

The key insight is that we need to maintain the elements in sorted order within the window to quickly find the middle element(s). But we also need to efficiently handle removals and insertions as the window moves.

If we re-sort the entire window every time it moves, that's O(k log k) per window, giving us O(n * k log k) total time - too slow for n=1e5.

But if we can maintain sorted order with efficient insertions and deletions (O(log k) each), we get O(n log k) total time - much better! The challenge is finding a data structure that supports both operations efficiently.

Think about maintaining a sorted list of numbers where you frequently need to:

1. Find the middle element(s) quickly
2. Remove a specific element (the one leaving the window)
3. Insert a new element (the one entering the window)

Two heaps (max-heap for smaller half, min-heap for larger half) or a balanced tree structure can maintain this sorted property while supporting O(log k) insertions and deletions. The median is always at the boundary between the two halves.

The optimal approach uses two heaps (or a balanced multiset) to maintain the window elements in sorted order. A max-heap stores the smaller half of elements, and a min-heap stores the larger half. As the window slides, we remove the outgoing element and insert the incoming element, both in O(log k) time. The median is always at the top of the heaps - either the max-heap's top (odd k) or the average of both tops (even k). This maintains sorted order without full re-sorting.

import heapq
from collections import defaultdict
def sliding_window_median(nums, k):
    """
    Calculate median of each sliding window of size k.
    Uses two heaps to maintain median efficiently.
    """
    result = []
    
    # Max heap for smaller half (negate values for max heap)
    max_heap = []
    # Min heap for larger half
    min_heap = []
    # Track elements to be removed (lazy deletion)
    to_remove = defaultdict(int)
    
    def add_element(num):
        """Add element to appropriate heap"""
        if not max_heap or num <= -max_heap[0]:
            heapq.heappush(max_heap, -num)
        else:
            heapq.heappush(min_heap, num)
    
    def remove_element(num):
        """Mark element for lazy removal"""
        to_remove[num] += 1
        if num <= -max_heap[0]:
            # Element is in max_heap
            pass
        else:
            # Element is in min_heap
            pass
    
    def clean_heap_top(heap, is_max_heap):
        """Remove invalid elements from heap top"""
        while heap:
            top = -heap[0] if is_max_heap else heap[0]
            if to_remove[top] > 0:
                to_remove[top] -= 1
                heapq.heappop(heap)
            else:
                break
    
    def rebalance_heaps():
        """Ensure heaps are balanced (size diff <= 1)"""
        # Clean tops first
        clean_heap_top(max_heap, True)
        clean_heap_top(min_heap, False)
        
        # Rebalance if needed
        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 get_median():
        """Calculate median from heap tops"""
        clean_heap_top(max_heap, True)
        clean_heap_top(min_heap, False)
        
        if k % 2 == 1:
            # Odd k: median is max_heap top
            return float(-max_heap[0])
        else:
            # Even k: median is average of both tops
            return (-max_heap[0] + min_heap[0]) / 2.0
    
    # Build initial window
    for i in range(k):
        add_element(nums[i])
        rebalance_heaps()
    
    # Get median of first window
    result.append(get_median())
    
    # Slide window through array
    for i in range(k, len(nums)):
        # Remove outgoing element
        outgoing = nums[i - k]
        remove_element(outgoing)
        
        # Add incoming element
        incoming = nums[i]
        add_element(incoming)
        
        # Rebalance and get median
        rebalance_heaps()
        result.append(get_median())
    
    return result

• Two-heap median maintenance: Use a max-heap for the smaller half and min-heap for the larger half of elements to maintain O(log k) median access - this pattern applies whenever you need dynamic median queries with insertions/deletions, as direct sorting would be O(k log k) per window.
• Lazy deletion with hash map: Track elements to be removed in a deletion counter map rather than immediately removing from heaps - only perform actual removal when the to-be-deleted element surfaces at a heap top, avoiding expensive O(k) heap searches while maintaining correctness.
• Heap rebalancing invariant: Maintain the property that max-heap size equals min-heap size (even k) or max-heap has one extra element (odd k) - check and rebalance after every insertion and lazy deletion to ensure the median is always at the heap tops.
• Integer overflow prevention: For even-sized windows, compute median as (left_max + right_min) / 2.0 rather than (left_max + right_min) / 2 to handle large integers correctly, and be careful with languages where heap operations might cause overflow when dealing with values near INT_MAX.
• Sliding window with deletion pattern: This add-new, remove-old, query pattern extends beyond medians to any sliding window aggregate (kth smallest, mode, range queries) where you need efficient online updates - consider augmented data structures like balanced BSTs or indexed heaps.
• Amortized complexity analysis: While individual operations might trigger multiple lazy deletions, each element is inserted once and deleted once across all windows, making the amortized time O(n log k) total rather than O(n²) - understanding amortization is crucial for analyzing streaming algorithms.