Sliding Window Median

Sliding Window Median asks for the median of every fixed-size window as it slides across an array. It is the running-median problem with an extra twist: elements do not just arrive, they also leave. The clean answer pairs two heaps with a lazy-deletion trick.

The slow way first

The obvious idea: for each window, copy out its k elements, sort them, and read the middle. That is O(n · k log k) — re-sorting every window from scratch throws away all the work from the previous one. For large k it is far too slow.

The question to ask: as the window slides by one, only one element enters and one leaves — can I keep the window pre-sorted and read the median instantly?

The idea: two heaps, balanced

Split the window in two. A max-heap low holds the smaller half; a min-heap high holds the larger half. Keep them balanced so low has the same size as high, or exactly one extra element. Then:

• For an odd window, the median is the top of low.
• For an even window, the median is the average of the two tops.

The twist: when a value leaves the window it may be buried deep inside a heap, and heaps cannot remove an arbitrary element cheaply. So we lazy-delete — record that the value is stale in a counter, and only actually pop it once it bubbles up to a heap top.

Walk through it

Step through the animation. The pointers L and R mark the window edges. Below, the two heap stacks fill and rebalance. Each time the window slides, the departing value (marked stale) is dropped only when it surfaces on top, and the median is read straight off the max-heap top.

Pseudocode

low  = empty max-heap   # smaller half of the window
high = empty min-heap   # larger half
stale = empty counter   # values that left but are still in a heap
for r from 0 to n-1:
    push nums[r] into the heaps, then rebalance their sizes
    if r >= k-1:                       # a full window exists
        record the median (heap tops)
        mark nums[r-k+1] as stale      # the value leaving the window
        pop any stale value sitting on a heap top
        rebalance the heap sizes again
return the list of medians

The Python solution

def median_sliding_window(nums, k):
    low, high = [], []          # max-heap (negated), min-heap
    stale = Counter()           # lazy-delete bookkeeping
    def rebalance():
        # keep len(low) == len(high) or len(low) == len(high)+1
        ...
    for r in range(len(nums)):
        push(nums[r])           # into low/high
        rebalance()
        if r >= k - 1:
            res.append(median(low, high, k))
            x = nums[r - k + 1] # value leaving the window
            stale[x] += 1       # mark for lazy deletion
            remove_stale_tops() # pop only when on top
            rebalance()
    return res

• low is a max-heap (Python only has min-heaps, so values are stored negated) holding the smaller half; high is a plain min-heap holding the larger half.
• stale is a counter of values that have left the window but are still physically inside a heap.
• push adds the new value to the correct heap; rebalance moves a top across if the sizes drift apart.
• When a window is complete, median reads the heap top(s) in O(1).
• x = nums[r - k + 1] is the value sliding out. We bump its stale count instead of searching for it.
• remove_stale_tops pops a heap top only when that exact value is marked stale — that is the lazy delete.

Complexity

Each slide does a constant number of heap operations, each O(log k), so the whole pass is O(n log k). The heaps hold at most a window plus a few stale entries, so space is O(k).

When this pattern shows up

Practice