Sliding Window Median — Data Structures & Algorithms

Problem Statement

Given an array nums and window size k, return the median of each contiguous window of size k as the window slides from left to right.

Input

An integer array and window size.

Example input

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

Output

An array of medians, one per window.

Expected output

[1, -1, -1, 3, 5, 6]
 
// windows: [1,3,-1]→1, [3,-1,-3]→-1,
//          [-1,-3,5]→-1, [-3,5,3]→3,
//          [5,3,6]→5, [3,6,7]→6

Constraints

1 ≤ k ≤ nums.length ≤ 10⁵
-2³¹ ≤ nums[i] ≤ 2³¹ − 1

Intuition

Extend the Two-Heaps median pattern. We also need to remove the leftmost element as the window slides — but heaps don’t support O(log n) random removal. Fix this with lazy deletion: track a dictionary of “to-be-deleted” values. When a heap’s root matches a pending deletion, pop-and-forget at that moment. Maintain heap balance using a virtual size counter that excludes pending deletions.

Each of the n window shifts does a constant number of heap operations, each O(log k). Lazy-deletion work amortises to O(1) per element since each element is deleted at most once.

Maintenance steps per shift

1. Insert the incoming value into the correct half.
2. Mark the outgoing value in the to_delete map and adjust virtual balance.
3. Rebalance based on virtual balance.
4. Prune — drop any root that is marked for deletion.
5. Read medians from the roots.

Solution

sliding_window_median.py

import heapq
from collections import defaultdict
 
def medianSlidingWindow(nums: list[int], k: int) -> list[float]:
    small: list[int] = []                # max-heap (negated) — lower half
    large: list[int] = []                # min-heap           — upper half
    to_delete: dict[int, int] = defaultdict(int)
    balance = 0                          # virtual (len(small) − len(large))
 
    def prune(heap: list[int]) -> None:
        sign = -1 if heap is small else 1
        while heap and to_delete[sign * heap[0]] > 0:
            to_delete[sign * heap[0]] -= 1
            heapq.heappop(heap)
 
    def get_median() -> float:
        return float(-small[0]) if k % 2 else (-small[0] + large[0]) / 2.0
 
    # initial window
    for x in nums[:k]:
        heapq.heappush(small, -x)
    for _ in range(k // 2):
        heapq.heappush(large, -heapq.heappop(small))
 
    result: list[float] = [get_median()]
 
    for i in range(k, len(nums)):
        incoming, outgoing = nums[i], nums[i - k]
 
        # insert incoming
        if incoming <= -small[0]:
            heapq.heappush(small, -incoming); balance += 1
        else:
            heapq.heappush(large, incoming);  balance -= 1
 
        # mark outgoing for deletion
        to_delete[outgoing] += 1
        if outgoing <= -small[0]: balance -= 1
        else:                     balance += 1
 
        # rebalance virtually
        if balance > 0:
            heapq.heappush(large, -heapq.heappop(small)); balance -= 2
        elif balance < 0:
            heapq.heappush(small, -heapq.heappop(large)); balance += 2
 
        prune(small); prune(large)
        result.append(get_median())
 
    return result

sliding_window_median.ts

function medianSlidingWindow(nums: number[], k: number): number[] {
  const small = maxHeap<number>();              // lower half
  const large = minHeap<number>();              // upper half
  const toDelete = new Map<number, number>();
  let balance = 0;                              // virtual size diff
 
  const prune = (heap: typeof small) => {
    while (heap.size > 0) {
      const top = heap.peek() as number;
      if ((toDelete.get(top) ?? 0) > 0) {
        toDelete.set(top, (toDelete.get(top) as number) - 1);
        heap.pop();
      } else break;
    }
  };
 
  const getMedian = (): number =>
    k % 2 === 1
      ? (small.peek() as number)
      : ((small.peek() as number) + (large.peek() as number)) / 2;
 
  for (let i = 0; i < k; i++) small.push(nums[i]);
  for (let i = 0; i < Math.floor(k / 2); i++) large.push(small.pop()!);
 
  const out: number[] = [getMedian()];
 
  for (let i = k; i < nums.length; i++) {
    const incoming = nums[i], outgoing = nums[i - k];
 
    if (incoming <= (small.peek() as number)) { small.push(incoming); balance++; }
    else                                       { large.push(incoming); balance--; }
 
    toDelete.set(outgoing, (toDelete.get(outgoing) ?? 0) + 1);
    if (outgoing <= (small.peek() as number)) balance--;
    else                                      balance++;
 
    if (balance > 0)      { large.push(small.pop()!); balance -= 2; }
    else if (balance < 0) { small.push(large.pop()!); balance += 2; }
 
    prune(small);
    prune(large);
    out.push(getMedian());
  }
  return out;
}

Complexity

Metric	Value	Reason
Time	`O(n log k)`	Each of `n` window shifts does a constant number of heap operations at `log k`. Lazy-deletion amortises to `O(1)` per element.
Space	`O(k)`	Both heaps plus the deletion map hold at most `k` live entries at any time.

Edge Case Thinking

Scenario	Handling
Integer overflow in median	`(a + b) / 2` may overflow 32-bit. Use `a / 2 + b / 2` in Java/C++. Python/JS floats are safe up to `2⁵³`.
`k == 1`	Every element is its own median; degenerate but correct.
`k == n`	Single median; equivalent to the global median.
Duplicates	Deletion map uses counts — each instance is deleted independently, preserving correctness.
Very wide value range	Comparisons don’t care about magnitude; 64-bit precision is plenty.