SLIDING WINDOW › FIXED SIZE SLIDING-WINDOW
Open — the attempt gate is not wired up yet
This editorial is meant to unlock after you have run the problem at least once, with the worked solution behind one further deliberate click. That needs per-learner unlock state nothing stores today, so for now the whole article is open.
Try it yourself first →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.
| 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). |
#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.
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.
#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.