What is the brute force approach and complexity for Sliding Window Median?

Copy each window, sort the copy, and read the middle with time complexity O(N · K log K) and space complexity O(K).

What is the optimal approach and complexity for Sliding Window Median?

Two heaps give the middle; a leaving value is marked and dropped only when it reaches a top with optimal time complexity O(N log N) and space complexity O(N).

How do you identify the pattern for Sliding Window Median?

Look for key signals in the prompt: "median of each window" indicates The middle of a set that keeps changing. Two heaps keep the middle at their tops.; "window of size k slides" indicates Values come in and go out. A plain running median only adds values, so it cannot handle leaving values.; "return the medians in window order" indicates One answer per window position. After each slide, read the tops..

Sliding Window Median

Hard·LeetCode #480Interview-Level

LeetCode

Jump:

30-Second Mental ModelTwo Heaps — Sliding median (two heaps + lazy deletion)

Complexity:O(N · K log K)→O(N log N)

Key Insight

Split the window into low, a max-heap with the smaller half, and high, a min-heap with the larger half. Their two tops are the middle. A heap cannot delete a value from its middle, so a leaving value is marked as stale in a delayed map. A stale value only matters when it reaches a top, so it is dropped then. A balance counter tracks valid values only.

Core Validity Invariant

The state is valid when low holds ceil(k/2) valid values, all ≤ every valid value in high, and neither top is stale.

Problem

You get an array of integers nums and a window size k. Put a window of size k at the left end of the array. Then slide it one step to the right at a time, until its right edge reaches the last element.

For each window position, find its median: sort the window's values and take the middle one. If the window has an even number of values, the median is the average of the two middle values.

Return the medians in window order. An answer within 10^-5 of the true value is accepted.

Input

An integer array nums and an integer k, the window size.

Output

An array of n − k + 1 numbers. Entry i is the median of the window that starts at index i.

Example 1

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

Output: [1, -1, -1, 3, 5, 6]

The windows are [1,3,-1], [3,-1,-3], [-1,-3,5], [-3,5,3], [5,3,6] and [3,6,7]. Their medians are 1, -1, -1, 3, 5 and 6.

Example 2

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

Output: [2, 3, 3, 3, 2, 3, 2]

Every window has 3 values, so the median is the middle one after sorting. For example [3,4,2] sorts to [2,3,4], and its median is 3.

Example 3

Input: nums = [5, 9], k = 2

Output: [7]

There is one window, the whole array. Its two middle values are 5 and 9, so the median is (5 + 9) / 2 = 7.

Constraints

• 1 ≤ k ≤ nums.length ≤ 10^5
• −2^31 ≤ nums[i] ≤ 2^31 − 1

First, think yourself

Before opening any solution, try to answer these on paper. Use hints only when stuck — each hint is counted.

1.
A median changes when values come and go. What data structure can give me the middle of a set quickly while the set changes?
2.
If I sorted every window again, how much of that work would repeat from one window to the next?
3.
A slide removes one value and adds one. Can I keep the window sorted and fix only the spots that changed?
4.
A priority_queue only shows me its top. What can I do when a value that is not on top has to leave?
5.
For an odd window size, how many values should the smaller half hold compared with the larger half? For an even size, which two values give the median?

Brute force approach

Idea

For every window, copy its k values, sort the copy, and read the middle value (or average the two middle values). There are n − k + 1 windows.

Thinking process

1
A median is read from a sorted list, so the simplest plan is to sort each window and read its middle.
2
Take the first window of the dry run, [6, 1, 9, 4] (k = 4). It sorts to [1, 4, 6, 9]. The two middle values are 4 and 6, so the median is (4 + 6) / 2 = 5.
3
The next window [1, 9, 4, 7] sorts to [1, 4, 7, 9]. The middle two are 4 and 7, so the median is (4 + 7) / 2 = 5.5.
4
Every window is sorted from scratch, even though it shares k − 1 = 3 values with the window before it.

Code & Implementation

brute.cpp

class Solution {
public:
    vector<double> medianSlidingWindow(vector<int>& nums, int k) {
        int n = nums.size();
        vector<double> ans;

        // Every window of size k, one at a time.
        for (int start = 0; start + k <= n; start++) {
            // Copy the window and sort the copy. The median is the middle value.
            vector<int> w(nums.begin() + start, nums.begin() + start + k);
            sort(w.begin(), w.end());

            if (k % 2 == 1) {
                ans.push_back(w[k / 2]);
            } else {
                // Two middle values: average them. Cast first, so two large ints cannot overflow.
                ans.push_back(((double)w[k / 2 - 1] + w[k / 2]) / 2.0);
            }
        }
        return ans;
    }
};

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

class Solution {
    public double[] medianSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        double[] ans = new double[n - k + 1];

        // Every window of size k, one at a time.
        for (int start = 0; start + k <= n; start++) {
            // Copy the window and sort the copy. The median is the middle value.
            List<Integer> w = new ArrayList<>();
            for (int i = start; i < start + k; i++) {
                w.add(nums[i]);
            }
            Collections.sort(w);

            if (k % 2 == 1) {
                ans[start] = w.get(k / 2);
            } else {
                // Two middle values: average them. Cast first, so two large ints cannot overflow.
                ans[start] = ((double) w.get(k / 2 - 1) + w.get(k / 2)) / 2.0;
            }
        }
        return ans;
    }
}

from typing import List

class Solution:
    def medianSlidingWindow(self, nums: List[int], k: int) -> List[float]:
        n = len(nums)
        ans: List[float] = []

        # Every window of size k, one at a time.
        for start in range(n - k + 1):
            # Copy the window and sort the copy. The median is the middle value.
            w = sorted(nums[start : start + k])

            if k % 2 == 1:
                ans.append(float(w[k // 2]))
            else:
                # Two middle values: average them.
                ans.append((w[k // 2 - 1] + w[k // 2]) / 2.0)

        return ans

export function medianSlidingWindow(nums: number[], k: number): number[] {
    const n = nums.length;
    const ans: number[] = [];

    // Every window of size k, one at a time.
    for (let start = 0; start + k <= n; start++) {
        // Copy the window and sort the copy. The median is the middle value.
        const w = nums.slice(start, start + k).sort((a, b) => a - b);

        if (k % 2 === 1) {
            ans.push(w[Math.floor(k / 2)]);
        } else {
            // Two middle values: average them.
            ans.push((w[Math.floor(k / 2) - 1] + w[Math.floor(k / 2)]) / 2.0);
        }
    }
    return ans;
}

Complexity

Time O(N · K log K)Space O(K)

There are about n windows, and each one costs a sort of k values. With n = 10^5 and k = 5·10^4, that is roughly 4·10^10 operations: far too slow.

Better approach

Why brute force is slow

Brute force sorts the whole window again for every start, even though only one value changed.

What repeated work are we doing?

The k − 1 values that stay in the window are sorted again and again. Their relative order never changes, so most of that sorting is wasted.

What information can we reuse?

Keep the window in sorted order. A binary search finds the one spot that changes, so each slide costs a search plus one shift, not a sort.

New approach

Idea

Keep the window as a sorted vector at all times. A new value goes in at its sorted spot, found by binary search. A leaving value is found by binary search and erased. Then the middle is read directly by its index.

Thinking process

1
A slide changes exactly one value in and one value out. So the window does not need a full re-sort.
2
Take the window [6, 1, 9, 4] sorted as [1, 4, 6, 9]. Remove 6 (binary search, then erase): [1, 4, 9]. Insert 7 at the spot that keeps the order: [1, 4, 7, 9].
3
The middle values sit at indexes k/2 − 1 = 1 and k/2 = 2, which are 4 and 7. The median is (4 + 7) / 2 = 5.5, the same as the brute force answer.
4
Binary search finds each spot in O(log K). The vector then shifts the values after that spot by one place, and that shift is the remaining cost.

Code & Implementation

better.cpp

class Solution {
public:
    vector<double> medianSlidingWindow(vector<int>& nums, int k) {
        int n = nums.size();
        vector<double> ans;

        // The current window, kept in sorted order at all times.
        vector<int> win;
        for (int i = 0; i < n; i++) {
            if (i >= k) {
                // The value leaving the window: binary search finds one copy, erase shifts the tail left.
                win.erase(lower_bound(win.begin(), win.end(), nums[i - k]));
            }
            // The new value: binary search finds its sorted spot, insert shifts the tail right.
            win.insert(upper_bound(win.begin(), win.end(), nums[i]), nums[i]);

            if (i >= k - 1) {
                // The window is sorted, so the middle is read by index.
                if (k % 2 == 1) {
                    ans.push_back(win[k / 2]);
                } else {
                    ans.push_back(((double)win[k / 2 - 1] + win[k / 2]) / 2.0);
                }
            }
        }
        return ans;
    }
};

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

class Solution {
    public double[] medianSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        double[] ans = new double[n - k + 1];

        // The current window, kept in sorted order at all times.
        List<Long> win = new ArrayList<>();
        int ansIdx = 0;

        for (int i = 0; i < n; i++) {
            if (i >= k) {
                // The value leaving the window: binary search finds one copy, remove shifts the tail left.
                long out = nums[i - k];
                int idx = Collections.binarySearch(win, out);
                if (idx >= 0) {
                    // In case of duplicates, find the first occurrence or any valid one
                    win.remove(idx);
                }
            }
            // The new value: binary search finds its sorted spot, insert shifts the tail right.
            long inVal = nums[i];
            int idx = Collections.binarySearch(win, inVal);
            if (idx < 0) {
                idx = -(idx + 1);
            } else {
                // upper_bound equivalent: skip all equal elements
                while (idx < win.size() && win.get(idx) == inVal) {
                    idx++;
                }
            }
            win.add(idx, inVal);

            if (i >= k - 1) {
                // The window is sorted, so the middle is read by index.
                if (k % 2 == 1) {
                    ans[ansIdx++] = win.get(k / 2);
                } else {
                    ans[ansIdx++] = ((double) win.get(k / 2 - 1) + win.get(k / 2)) / 2.0;
                }
            }
        }
        return ans;
    }
}

import bisect
from typing import List

class Solution:
    def medianSlidingWindow(self, nums: List[int], k: int) -> List[float]:
        n = len(nums)
        ans: List[float] = []

        # The current window, kept in sorted order at all times.
        win: List[int] = []
        for i in range(n):
            if i >= k:
                # The value leaving the window: binary search finds one copy, erase shifts the tail left.
                idx = bisect.bisect_left(win, nums[i - k])
                win.pop(idx)
            # The new value: binary search finds its sorted spot, insert shifts the tail right.
            idx = bisect.bisect_right(win, nums[i])
            win.insert(idx, nums[i])

            if i >= k - 1:
                # The window is sorted, so the middle is read by index.
                if k % 2 == 1:
                    ans.append(float(win[k // 2]))
                else:
                    ans.append((win[k // 2 - 1] + win[k // 2]) / 2.0)

        return ans

export function medianSlidingWindow(nums: number[], k: number): number[] {
    const n = nums.length;
    const ans: number[] = [];

    // The current window, kept in sorted order at all times.
    const win: number[] = [];

    function lowerBound(arr: number[], target: number): number {
        let left = 0;
        let right = arr.length;
        while (left < right) {
            const mid = (left + right) >> 1;
            if (arr[mid] < target) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left;
    }

    function upperBound(arr: number[], target: number): number {
        let left = 0;
        let right = arr.length;
        while (left < right) {
            const mid = (left + right) >> 1;
            if (arr[mid] <= target) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left;
    }

    for (let i = 0; i < n; i++) {
        if (i >= k) {
            // The value leaving the window: binary search finds one copy, erase shifts the tail left.
            const eraseIdx = lowerBound(win, nums[i - k]);
            win.splice(eraseIdx, 1);
        }
        // The new value: binary search finds its sorted spot, insert shifts the tail right.
        const insertIdx = upperBound(win, nums[i]);
        win.splice(insertIdx, 0, nums[i]);

        if (i >= k - 1) {
            // The window is sorted, so the middle is read by index.
            if (k % 2 === 1) {
                ans.push(win[Math.floor(k / 2)]);
            } else {
                ans.push((win[Math.floor(k / 2) - 1] + win[Math.floor(k / 2)]) / 2.0);
            }
        }
    }
    return ans;
}

Complexity

Time O(N · K)Space O(K)

Each slide shifts up to k values, so the worst case is about n · k moves. That is much faster than sorting, but still too slow for n = 10^5 with a large k. The optimal approach gets O(N log N) with two heaps.

Optimized approach

Idea

Start from brute force

Brute force sorts each window from scratch, so the work done for one window is never reused by the next.

Find the repeated work

Only one value enters and one leaves per slide, so the other k − 1 values keep their order. A heap also cannot delete a value that is not on top, so the leaving value needs another way to be forgotten.

Define the state — what variables do I need?

low: Max-heap with the smaller half of the window. Its top is the largest value in that half. Stale values may sit deeper inside it.
high: Min-heap with the larger half. Its top is the smallest value in that half. Stale values may sit deeper inside it.
delayed: Map from a value to the number of copies that left the window but are still in a heap.
balance: (valid values in low) − (valid values in high). Stale values never count, so balance is always 0 or 1 after a full step.

Define validity

The state is valid when low holds ceil(k/2) valid values, all ≤ every valid value in high, and neither top is stale.

Define the transitions — when does each pointer move, and why is it safe?

A value `v` leaves (`v = nums[i − k]`) and `v ≤ low.top()`

balance−−; delayed[v]++; then prune(low)

v was a valid value of low, so low now has one fewer valid value. Its copy is marked stale, and prune(low) drops it right away if it is on top.

A value `v` leaves and `v > low.top()` (or low is empty)

balance++; delayed[v]++; then prune(high)

v was a valid value of high, so high has one fewer valid value.

A value `v` enters

If low is empty or v ≤ low.top(), push v to low and balance++. Otherwise push v to high and balance−−.

v joins the half its value belongs to, so every valid low value stays ≤ every valid high value.

balance > 1 or balance < 0 (after a leave or an enter)

If balance > 1, move low's top to high, balance −= 2, then prune(low). If balance < 0, move high's top to low, balance += 2, then prune(high).

Each step changes balance by one, so one move is always enough. The moved value is a valid top, so the order between the halves still holds.

The window is full (i ≥ k − 1)

median = low.top() if k is odd, otherwise (low.top() + high.top()) / 2

Both tops are valid and the counts are exact, so these are the middle values of the window.

What does the current window add to the answer?

Each full window gives one answer, read from the two tops after its last slide. Windows are visited in order, so the answers come out in order.

Code & Implementation

optimal.cpp

class Solution {
public:
    vector<double> medianSlidingWindow(vector<int>& nums, int k) {
        int n = nums.size();

        // low: max-heap with the smaller half. high: min-heap with the larger half.
        priority_queue<int> low;
        priority_queue<int, vector<int>, greater<int>> high;

        // Lazy deletion: a value that left the window stays in its heap until it reaches a top.
        // delayed[v] = how many copies of v must still be dropped.
        unordered_map<int, int> delayed;

        // (valid items in low) - (valid items in high). Stale items are not counted.
        int balance = 0;

        // Drop stale copies sitting on top. Stale copies deeper down wait until they surface.
        auto prune = [&](auto& heap) {
            while (!heap.empty()) {
                auto it = delayed.find(heap.top());
                if (it == delayed.end()) break;
                if (--it->second == 0) delayed.erase(it);
                heap.pop();
            }
        };

        // Keep balance in {0, 1}: low holds ceil(size / 2) valid items, so its top is the median.
        // One step changes balance by 1, so one move is always enough.
        auto rebalance = [&]() {
            if (balance > 1) {                  // low has 2 too many: move its top to high
                high.push(low.top());
                low.pop();
                balance -= 2;
                prune(low);
            } else if (balance < 0) {           // high has 1 too many: move its top to low
                low.push(high.top());
                high.pop();
                balance += 2;
                prune(high);
            }
        };

        vector<double> ans;
        for (int i = 0; i < n; i++) {
            if (i >= k) {
                int out = nums[i - k];
                // The leaving value sits in low exactly when it is <= low's top.
                if (!low.empty() && out <= low.top()) {
                    balance--;
                    delayed[out]++;
                    prune(low);                 // low first: if out is its top, this is the copy we mark
                } else {
                    balance++;
                    delayed[out]++;
                    prune(high);
                }
                rebalance();
            }

            // The new value goes to low if it is <= low's top, else to high.
            if (low.empty() || nums[i] <= low.top()) {
                low.push(nums[i]);
                balance++;
            } else {
                high.push(nums[i]);
                balance--;
            }
            rebalance();

            if (i >= k - 1) {
                // Both tops are valid here, so they are the real middle values.
                if (k % 2 == 1) {
                    ans.push_back((double)low.top());
                } else {
                    // Cast before adding: two values near 2^31 would overflow an int sum.
                    ans.push_back(((double)low.top() + high.top()) / 2.0);
                }
            }
        }
        return ans;
    }
};

import java.util.Collections;
import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;

class Solution {
    private void prune(PriorityQueue<Integer> heap, Map<Integer, Integer> delayed) {
        while (!heap.isEmpty()) {
            int top = heap.peek();
            if (!delayed.containsKey(top)) break;
            int count = delayed.get(top);
            if (count == 1) {
                delayed.remove(top);
            } else {
                delayed.put(top, count - 1);
            }
            heap.poll();
        }
    }

    public double[] medianSlidingWindow(int[] nums, int k) {
        int n = nums.length;

        // low: max-heap with the smaller half. high: min-heap with the larger half.
        PriorityQueue<Integer> low = new PriorityQueue<>(Collections.reverseOrder());
        PriorityQueue<Integer> high = new PriorityQueue<>();

        // Lazy deletion: a value that left the window stays in its heap until it reaches a top.
        // delayed[v] = how many copies of v must still be dropped.
        Map<Integer, Integer> delayed = new HashMap<>();

        // (valid items in low) - (valid items in high). Stale items are not counted.
        int balance = 0;

        double[] ans = new double[n - k + 1];
        int ansIdx = 0;

        for (int i = 0; i < n; i++) {
            if (i >= k) {
                int out = nums[i - k];
                // The leaving value sits in low exactly when it is <= low's top.
                if (!low.isEmpty() && out <= low.peek()) {
                    balance--;
                    delayed.put(out, delayed.getOrDefault(out, 0) + 1);
                    prune(low, delayed); // low first: if out is its top, this is the copy we mark
                } else {
                    balance++;
                    delayed.put(out, delayed.getOrDefault(out, 0) + 1);
                    prune(high, delayed);
                }
                if (balance > 1) {
                    high.offer(low.poll());
                    balance -= 2;
                    prune(low, delayed);
                } else if (balance < 0) {
                    low.offer(high.poll());
                    balance += 2;
                    prune(high, delayed);
                }
            }

            // The new value goes to low if it is <= low's top, else to high.
            if (low.isEmpty() || nums[i] <= low.peek()) {
                low.offer(nums[i]);
                balance++;
            } else {
                high.offer(nums[i]);
                balance--;
            }
            if (balance > 1) {
                high.offer(low.poll());
                balance -= 2;
                prune(low, delayed);
            } else if (balance < 0) {
                low.offer(high.poll());
                balance += 2;
                prune(high, delayed);
            }

            if (i >= k - 1) {
                // Both tops are valid here, so they are the real middle values.
                if (k % 2 == 1) {
                    ans[ansIdx++] = (double) low.peek();
                } else {
                    // Cast before adding: two values near 2^31 would overflow an int sum.
                    ans[ansIdx++] = ((double) low.peek() + high.peek()) / 2.0;
                }
            }
        }
        return ans;
    }
}

from collections import defaultdict
import heapq
from typing import Dict, List

class Solution:
    def medianSlidingWindow(self, nums: List[int], k: int) -> List[float]:
        n = len(nums)

        # low: max-heap with the smaller half. high: min-heap with the larger half.
        low: List[int] = []   # max-heap via negative numbers
        high: List[int] = []  # min-heap

        # Lazy deletion: a value that left the window stays in its heap until it reaches a top.
        # delayed[v] = how many copies of v must still be dropped.
        delayed: Dict[int, int] = defaultdict(int)

        # (valid items in low) - (valid items in high). Stale items are not counted.
        balance = 0

        # Drop stale copies sitting on top. Stale copies deeper down wait until they surface.
        def prune_low():
            while low and delayed.get(-low[0], 0) > 0:
                delayed[-low[0]] -= 1
                heapq.heappop(low)

        def prune_high():
            while high and delayed.get(high[0], 0) > 0:
                delayed[high[0]] -= 1
                heapq.heappop(high)

        # Keep balance in {0, 1}: low holds ceil(size / 2) valid items, so its top is the median.
        # One step changes balance by 1, so one move is always enough.
        def rebalance():
            nonlocal balance
            if balance > 1:  # low has 2 too many: move its top to high
                val = -heapq.heappop(low)
                heapq.heappush(high, val)
                balance -= 2
                prune_low()
            elif balance < 0:  # high has 1 too many: move its top to low
                val = heapq.heappop(high)
                heapq.heappush(low, -val)
                balance += 2
                prune_high()

        ans: List[float] = []
        for i in range(n):
            if i >= k:
                out = nums[i - k]
                # The leaving value sits in low exactly when it is <= low's top.
                if low and out <= -low[0]:
                    balance -= 1
                    delayed[out] += 1
                    prune_low()  # low first: if out is its top, this is the copy we mark
                else:
                    balance += 1
                    delayed[out] += 1
                    prune_high()
                rebalance()

            # The new value goes to low if it is <= low's top, else to high.
            if not low or nums[i] <= -low[0]:
                heapq.heappush(low, -nums[i])
                balance += 1
            else:
                heapq.heappush(high, nums[i])
                balance -= 1
            rebalance()

            if i >= k - 1:
                # Both tops are valid here, so they are the real middle values.
                if k % 2 == 1:
                    ans.append(float(-low[0]))
                else:
                    # Two middle values: average them.
                    ans.append((-low[0] + high[0]) / 2.0)

        return ans

class PriorityQueue<T> {
    private heap: T[] = [];
    constructor(private compare: (a: T, b: T) => number) {}

    push(val: T): void {
        this.heap.push(val);
        this.bubbleUp(this.heap.length - 1);
    }

    pop(): T | undefined {
        if (this.heap.length === 0) return undefined;
        const top = this.heap[0];
        const bottom = this.heap.pop()!;
        if (this.heap.length > 0) {
            this.heap[0] = bottom;
            this.bubbleDown(0);
        }
        return top;
    }

    peek(): T | undefined {
        return this.heap[0];
    }

    size(): number {
        return this.heap.length;
    }

    isEmpty(): boolean {
        return this.heap.length === 0;
    }

    private bubbleUp(idx: number): void {
        while (idx > 0) {
            const p = (idx - 1) >> 1;
            if (this.compare(this.heap[idx], this.heap[p]) < 0) {
                [this.heap[idx], this.heap[p]] = [this.heap[p], this.heap[idx]];
                idx = p;
            } else {
                break;
            }
        }
    }

    private bubbleDown(idx: number): void {
        const len = this.heap.length;
        while (true) {
            let smallest = idx;
            const left = 2 * idx + 1;
            const right = 2 * idx + 2;
            if (left < len && this.compare(this.heap[left], this.heap[smallest]) < 0) {
                smallest = left;
            }
            if (right < len && this.compare(this.heap[right], this.heap[smallest]) < 0) {
                smallest = right;
            }
            if (smallest !== idx) {
                [this.heap[idx], this.heap[smallest]] = [this.heap[smallest], this.heap[idx]];
                idx = smallest;
            } else {
                break;
            }
        }
    }
}

export function medianSlidingWindow(nums: number[], k: number): number[] {
    const n = nums.length;

    // low: max-heap with the smaller half. high: min-heap with the larger half.
    const low = new PriorityQueue<number>((a, b) => b - a);
    const high = new PriorityQueue<number>((a, b) => a - b);

    // Lazy deletion: a value that left the window stays in its heap until it reaches a top.
    // delayed[v] = how many copies of v must still be dropped.
    const delayed = new Map<number, number>();

    // (valid items in low) - (valid items in high). Stale items are not counted.
    let balance = 0;

    // Drop stale copies sitting on top. Stale copies deeper down wait until they surface.
    const prune = (heap: PriorityQueue<number>) => {
        while (!heap.isEmpty()) {
            const top = heap.peek()!;
            const count = delayed.get(top);
            if (!count) break;
            if (count === 1) {
                delayed.delete(top);
            } else {
                delayed.set(top, count - 1);
            }
            heap.pop();
        }
    };

    // Keep balance in {0, 1}: low holds ceil(size / 2) valid items, so its top is the median.
    // One step changes balance by 1, so one move is always enough.
    const rebalance = () => {
        if (balance > 1) { // low has 2 too many: move its top to high
            high.push(low.pop()!);
            balance -= 2;
            prune(low);
        } else if (balance < 0) { // high has 1 too many: move its top to low
            low.push(high.pop()!);
            balance += 2;
            prune(high);
        }
    };

    const ans: number[] = [];
    for (let i = 0; i < n; i++) {
        if (i >= k) {
            const out = nums[i - k];
            // The leaving value sits in low exactly when it is <= low's top.
            if (!low.isEmpty() && out <= low.peek()!) {
                balance--;
                delayed.set(out, (delayed.get(out) || 0) + 1);
                prune(low); // low first: if out is its top, this is the copy we mark
            } else {
                balance++;
                delayed.set(out, (delayed.get(out) || 0) + 1);
                prune(high);
            }
            rebalance();
        }

        // The new value goes to low if it is <= low's top, else to high.
        if (low.isEmpty() || nums[i] <= low.peek()!) {
            low.push(nums[i]);
            balance++;
        } else {
            high.push(nums[i]);
            balance--;
        }
        rebalance();

        if (i >= k - 1) {
            // Both tops are valid here, so they are the real middle values.
            if (k % 2 === 1) {
                ans.push(low.peek()!);
            } else {
                // Cast before adding, average of the two middle numbers
                ans.push((low.peek()! + high.peek()!) / 2.0);
            }
        }
    }
    return ans;
}

Complexity

Time O(N log N)Space O(N)

Stale values can pile up deep in a heap, so the two heaps can hold up to N items in total. The two-multiset version (one std::multiset per half, with the median read from iterators) is also O(N log K), since it only ever holds the k values of the window. Both are good; this one avoids iterator bookkeeping.

Why does this algorithm work?

Dry run

All approaches compared

Approach	Idea	Time	Space
Brute Force	Copy each window, sort the copy, and read the middle	O(N · K log K)	O(K)
Better	Binary search finds the spot for each insert and erase, so the window stays sorted	O(N · K)	O(K)
Optimal	Two heaps give the middle; a leaving value is marked and dropped only when it reaches a top	O(N log N)	O(N)

Why does this belong to this pattern?

Clues in the problem statement

“median of each window”The middle of a set that keeps changing. Two heaps keep the middle at their tops.
“window of size k slides”Values come in and go out. A plain running median only adds values, so it cannot handle leaving values.
“return the medians in window order”One answer per window position. After each slide, read the tops.

Median of a moving set+two heaps for the two halves+lazy deletion for leaving values→Two Heaps — Sliding median (two heaps + lazy deletion)

Find Median from Data Stream only inserts, so two heaps with no deletions are enough there. This question also has values that leave the window, and a heap cannot remove a value from its middle. The fix is lazy deletion: a leaving value is only marked, and it is dropped when it reaches a top. The validity rule also differs from that neighbour: a value inside a heap is not always in the window, so only the values still in the window count toward balance.

Don't make this mistake

Pattern confusion: a stale value still counted in the sizes

✗ delayed[out]++; prune(high); // balance is not changed

✓ balance++; // high loses a valid value delayed[out]++; prune(high);

This is the running-median habit. A heap cannot erase from its middle, so the code marks the value and prunes the top, but it forgets to fix the count. Dry run: nums = [6, 1, 9, 4, 7, 3, 8, 2, 5], k = 4. The window [6, 1, 9, 4] has low {1, 4} and high {6, 9}, with balance 0. When 6 leaves, it is on top of high and gets pruned. With balance still 0, the code thinks the halves are level, but high has lost a value. Then 7 enters high, balance drops to −1, and the rebalance moves 7 into low. The median of the window [1, 9, 4, 7] comes out as (7 + 9) / 2 = 8. The right answer is (4 + 7) / 2 = 5.5.

Reading a top without pruning it first

✗ balance++; delayed[out]++; // no prune(high)

✓ balance++; delayed[out]++; prune(high);

A stale value on top looks like a valid value to the code. Same dry run: after 6 leaves, high is {6, 9}, and 7 enters, so high becomes {6, 7, 9} with the stale 6 on top. The median then reads (4 + 6) / 2 = 5 for the window [1, 9, 4, 7], but the right answer is 5.5. Prune the side a value left from, right away, so its top is always valid.

Using < instead of <= when a leaving value ties with low's top

✗ if (!low.empty() && out < low.top()) {

✓ if (!low.empty() && out <= low.top()) {

A value equal to low's top is still a valid value of low, because low holds the smaller half. With <, the code takes it off high's count instead. For nums = [1, 4, 2, 0, 3] and k = 4, the window [1, 4, 2, 0] has low {0, 1} with top 1. When 1 leaves, it must be counted on the low side. The next window [4, 2, 0, 3] then has median (2 + 3) / 2 = 2.5, but the wrong code returns 1.5.

Averaging two ints overflows

✗ ans.push_back((low.top() + high.top()) / 2.0);

✓ ans.push_back(((double)low.top() + high.top()) / 2.0);

The sum is calculated as an int before the division. With nums = [2147483647, 2147483647] and k = 2, the sum 4294967294 does not fit in an int. In practice it wraps to −2, and the answer becomes −1.0. The right answer is 2147483647.0. Cast one value to double before the addition.

Want to implement this?

Write it yourself on LeetCode, then come back and compare your code with the solutions above.

Open coding workspace

How did it go?

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like Two Heaps translate into production architectures and low-level memory mechanics.

LLD Architecture

Real-time Metrics & Rolling Percentiles

Calculating streaming median and P99 latency in production telemetry systems.

Explore Track

C++ Internals

Smart Pointers & Ownership Semantics

Managing node ownership without memory leaks across priority queues.

Explore Track