Sliding Window Median — Editorial

Opening the reading…

Intuitionthe median is the boundary between two ordered halves

A window's median depends only on its sorted middle positions. If k is odd, the answer is the largest value in the lower half. If k is even, it is the average of that value and the smallest value in the upper half. The rest of the window matters only because it determines which values belong on each side of that boundary.

Keep the current window split into two multisets: left contains the smaller half and right contains the larger half. Maintain three facts after every update: every value in left is no greater than every value in right, left has either the same number of values as right or one extra, and both sets contain exactly the current window. Then the median is always at one or two set boundaries.

Approachinsert, remove, restore the partition, then read its boundary

Create left and right as multisets so equal values are stored separately and any departing value can be erased in logarithmic time; a set would lose duplicates and make the window contents incorrect.

For each nums[i], insert it into left when left is empty or the value is no greater than left's largest value, otherwise insert it into right; this keeps the new value on the side suggested by the current partition.

Balance immediately after insertion by moving left's largest value to right when left is too large, or right's smallest value to left when right is larger; without this, the boundary would no longer represent the middle positions.

When i is at least k, remove nums[i - k], the element just outside the new window, from whichever multiset contains one copy of it; finding and erasing one iterator preserves other equal values.

Balance again after removal because deleting from either side can leave a size difference of two or make right larger; moving only the boundary value repairs the size relation without breaking sorted order.

When i is at least k - 1, the first complete window exists, so read left's largest value for odd k or average the largest left value and smallest right value for even k; recording earlier would use fewer than k elements.

Return the collected medians after the scan, because each index contributes exactly one answer once the window ending at that index is complete.

Complexityevery update touches only ordered-set boundaries

MEASURE	BOUND	WHY
Time	O(n log k)	Each of the n values is inserted once and, except for the final window's values, removed once. A multiset operation costs O(log k) because it contains at most k values, and each rebalance moves a boundary value only a constant number of times per update.
Space	O(k) extra	The two multisets together contain at most k active values, so their storage is O(k). The output array is required output and is excluded from the extra-space bound. When the window is as large as the whole input, k equals n and this becomes O(n).

Here n is nums.length and k is the window size. The logarithm is base 2, though its base does not change the asymptotic bound.

Annotated solutionC++ · two multisets · arbitrary deletion stays simple

CPPMaintain the ordered partition, delete one outgoing copy, and read the exposed middle values.

#include <algorithm>
#include <set>
#include <vector>

using namespace std;

class Solution {
public:
    vector<double> medianSlidingWindow(vector<int>& nums, int k) {
        multiset<int> left, right;
        vector<double> ans;

        auto balance = [&]() {
            while (left.size() > right.size() + 1) {
                auto it = prev(left.end());
                right.insert(*it);
                left.erase(it);
            }
            while (right.size() > left.size()) {
                auto it = right.begin();
                left.insert(*it);
                right.erase(it);
            }
        };

        for (int i = 0; i < static_cast<int>(nums.size()); ++i) {
            if (left.empty() || nums[i] <= *left.rbegin()) {
                left.insert(nums[i]);
            } else {
                right.insert(nums[i]);
            }
            balance();

            if (i >= k) {
                int outgoing = nums[i - k];
                auto it = left.find(outgoing);
                if (it != left.end()) {
                    left.erase(it);
                } else {
                    right.erase(right.find(outgoing));
                }
                balance();
            }

            if (i >= k - 1) {
                if (k % 2 == 1) {
                    ans.push_back(static_cast<double>(*left.rbegin()));
                } else {
                    double lower = *left.rbegin();
                    double upper = *right.begin();
                    ans.push_back((lower + upper) / 2.0);
                }
            }
        }

        return ans;
    }
};

The insertion comparison uses left's largest value because that is the only boundary needed to decide the side. The removal uses find rather than erase by value alone: multiset::find gives one iterator, so deleting one occurrence cannot accidentally remove all equal values. The two balance loops are deliberately after removal as well as insertion, since either update can disturb the size invariant.

The heap alternativeless deletion-friendly, but a standard way to avoid ordered sets

Two heaps can represent the same partition: a max-heap for left and a min-heap for right. The difficulty is deleting the value that leaves the window, because a heap exposes only its top. Lazy deletion solves that by marking outgoing indices and discarding marked entries whenever they reach a heap top. This is an optimisation in library choice, not in asymptotic complexity: it still costs O(n log k) time and O(k) extra space.

CPPHeap version with index-based lazy deletion and explicit logical sizes.

#include <functional>
#include <queue>
#include <vector>

using namespace std;

class Solution {
    using Item = pair<int, int>;

public:
    vector<double> medianSlidingWindow(vector<int>& nums, int k) {
        priority_queue<Item> left;
        priority_queue<Item, vector<Item>, greater<Item>> right;
        vector<char> removed(nums.size(), false);
        vector<char> side(nums.size(), 0);
        vector<double> ans;
        int leftSize = 0;
        int rightSize = 0;

        auto pruneLeft = [&]() {
            while (!left.empty() && removed[left.top().second]) {
                left.pop();
            }
        };
        auto pruneRight = [&]() {
            while (!right.empty() && removed[right.top().second]) {
                right.pop();
            }
        };
        auto balance = [&]() {
            pruneLeft();
            pruneRight();
            while (leftSize > rightSize + 1) {
                Item item = left.top();
                left.pop();
                right.push(item);
                side[item.second] = 1;
                --leftSize;
                ++rightSize;
                pruneLeft();
            }
            while (rightSize > leftSize) {
                Item item = right.top();
                right.pop();
                left.push(item);
                side[item.second] = 0;
                --rightSize;
                ++leftSize;
                pruneRight();
            }
        };

        for (int i = 0; i < static_cast<int>(nums.size()); ++i) {
            pruneLeft();
            if (left.empty() || nums[i] <= left.top().first) {
                left.push({nums[i], i});
                side[i] = 0;
                ++leftSize;
            } else {
                right.push({nums[i], i});
                side[i] = 1;
                ++rightSize;
            }
            balance();

            if (i >= k) {
                int outgoing = i - k;
                removed[outgoing] = true;
                if (side[outgoing] == 0) {
                    --leftSize;
                } else {
                    --rightSize;
                }
                balance();
            }

            if (i >= k - 1) {
                pruneLeft();
                pruneRight();
                if (k % 2 == 1) {
                    ans.push_back(static_cast<double>(left.top().first));
                } else {
                    double lower = left.top().first;
                    double upper = right.top().first;
                    ans.push_back((lower + upper) / 2.0);
                }
            }
        }

        return ans;
    }
};

The heap version stores an index with every value, so equal numbers remain distinguishable when one leaves. The side array records which logical half owns that index; removed heap entries are not counted again, even if they remain buried. This saves the ordered-set dependency but adds bookkeeping and makes the invariant harder to inspect, so multisets are usually the clearer default.