Sliding Window Median

The median is the middle value in an ordered integer list. If the size of the list is even, there is no middle value. So the median is the mean of the two middle values.

480. Sliding Window Median

Difficulty: Hard

Problem Statement

The median is the middle value in an ordered list of numbers.

• If the list has an odd number of values, the median is the single middle value.
• If the list has an even number of values, there is no single middle value. In this case, the median is the average of the two middle values.

For example:

• If arr = [2, 3, 4], the median is 3.
• If arr = [1, 2, 3, 4], the median is (2 + 3) / 2 = 2.5.

You are given an integer array nums and an integer k.

There is a sliding window of size k. It moves across the array, from the very left to the very right. At any moment, you can only see the k numbers inside the window. Each time, the window moves one position to the right.

Return the median for each window position, as an array. Any answer within 10⁻⁵ of the correct value will be accepted.

Examples

Example 1

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

Output: [1.00000, -1.00000, -1.00000, 3.00000, 5.00000, 6.00000]

Explanation:

Window position                Median
---------------                -----
[1  3  -1] -3  5  3  6  7        1
 1 [3  -1  -3] 5  3  6  7       -1
 1  3 [-1  -3  5] 3  6  7       -1
 1  3  -1 [-3  5  3] 6  7        3
 1  3  -1  -3 [5  3  6] 7        5
 1  3  -1  -3  5 [3  6  7]       6

Example 2

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

Output: [2.00000, 3.00000, 3.00000, 3.00000, 2.00000, 3.00000, 2.00000]

Constraints

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

Solution

The main idea is to use two heaps:

• A max heap, which stores the smaller half of the numbers in the current window.
• A min heap, which stores the larger half of the numbers in the current window.

Inserting a New Number

When a new number comes into the window:

• If it is smaller than or equal to the top of the max heap, it goes into the max heap.
• Otherwise, it goes into the min heap.

The Tricky Part: Removing Numbers

As the window slides, we also need to remove the number that falls out of the window. But most heaps don't support removing a number from the middle — only from the top.

To handle this, we use a technique called lazy deletion:

• Instead of removing the number right away, we just mark it for deletion using a map.
• We only actually remove it once it reaches the top of one of the heaps.
• This means each heap may have some "stale" (already-deleted) values sitting near the top. We clean these up whenever we look at the top of a heap.

Keeping the Heaps Balanced

Every time we insert or mark-for-deletion a number, we rebalance the two heaps:

• If the max heap has more than one extra element compared to the min heap, we move the top of the max heap into the min heap. Then we clean up any stale entries at the new top.
• If the min heap has more elements than the max heap, we move the top of the min heap into the max heap. Then we clean up any stale entries at the new top.

This keeps both heaps balanced in size, so the median is always easy to find at the top of the heaps.

Building the First Window and Sliding

• For the first k numbers, we insert them all into our heaps. Then we calculate the median and add it to our result.
• For every number after that:
  • We insert the new number that just entered the window.
  • We mark the number that just left the window (the one k positions back) for deletion.
  • We calculate the new median and add it to our result.

Finding the Median

• If the window size k is odd, the median is just the top of the max heap.
• If k is even, the median is the average of the top of the max heap and the top of the min heap.

Code

class Heap {
  constructor(comparator) {
    this.heap = [];
    this.comparator = comparator;
  }
  size() { return this.heap.length; }
  isEmpty() { return this.heap.length === 0; }
  peek() { return this.heap[0]; }

  push(val) {
    this.heap.push(val);
    this._up(this.heap.length - 1);
  }

  pop() {
    const top = this.heap[0];
    const last = this.heap.pop();
    if (this.heap.length > 0) {
      this.heap[0] = last;
      this._down(0);
    }
    return top;
  }

  _up(i) {
    while (i > 0) {
      const p = (i - 1) >> 1;
      if (this.comparator(this.heap[p], this.heap[i]) <= 0) break;
      [this.heap[p], this.heap[i]] = [this.heap[i], this.heap[p]];
      i = p;
    }
  }

  _down(i) {
    const n = this.heap.length;
    while (true) {
      const l = 2 * i + 1, r = 2 * i + 2;
      let best = i;
      if (l < n && this.comparator(this.heap[l], this.heap[best]) < 0) best = l;
      if (r < n && this.comparator(this.heap[r], this.heap[best]) < 0) best = r;
      if (best === i) break;
      [this.heap[i], this.heap[best]] = [this.heap[best], this.heap[i]];
      i = best;
    }
  }
}

class DualHeap {
  constructor() {
    this.small = new Heap((a, b) => b - a); // max-heap: lower half
    this.large = new Heap((a, b) => a - b); // min-heap: upper half
    this.delayed = new Map();               // num -> pending removal count
    this.smallSize = 0;                     // true logical size, excluding stale entries
    this.largeSize = 0;
  }

  // Discard stale (already-erased) entries sitting on top of a heap
  prune(heap) {
    while (!heap.isEmpty() && this.delayed.has(heap.peek())) {
      const num = heap.peek();
      this.delayed.set(num, this.delayed.get(num) - 1);
      if (this.delayed.get(num) === 0) this.delayed.delete(num);
      heap.pop();
    }
  }

  makeBalanced() {
    if (this.smallSize > this.largeSize + 1) {
      this.large.push(this.small.pop());
      this.smallSize--;
      this.largeSize++;
      this.prune(this.small);
    } else if (this.smallSize < this.largeSize) {
      this.small.push(this.large.pop());
      this.largeSize--;
      this.smallSize++;
      this.prune(this.large);
    }
  }

  insert(num) {
    if (this.small.isEmpty() || num <= this.small.peek()) {
      this.small.push(num);
      this.smallSize++;
    } else {
      this.large.push(num);
      this.largeSize++;
    }
    this.makeBalanced();
  }

  erase(num) {
    this.delayed.set(num, (this.delayed.get(num) || 0) + 1);
    if (num <= this.small.peek()) {
      this.smallSize--;
      if (num === this.small.peek()) this.prune(this.small);
    } else {
      this.largeSize--;
      if (num === this.large.peek()) this.prune(this.large);
    }
    this.makeBalanced();
  }

  getMedian(k) {
    return k % 2 === 1
      ? this.small.peek()
      : (this.small.peek() + this.large.peek()) / 2;
  }
}

var medianSlidingWindow = function (nums, k) {
  const dh = new DualHeap();

  for (let i = 0; i < k; i++) {
    dh.insert(nums[i]);
  }

  const result = [dh.getMedian(k)];

  for (let i = k; i < nums.length; i++) {
    dh.insert(nums[i]);
    dh.erase(nums[i - k]);
    result.push(dh.getMedian(k));
  }

  return result;
};