# C++ two multiset solution

• Similar idea as 295. Find Median from Data Stream
Keep a max heap and a min heap
But in this case, we need to keep on removing elements out of the window
So use multiset insead of heap
T = O(n*log(k)), S = O(k)

``````class Solution {
public:
vector<double> medianSlidingWindow(vector<int>& nums, int k) {
vector<double> res;
multiset<int> u, l;
int n = nums.size();
for (int i = 0; i < n; ++i) {

// Insert new number
if (u.empty() or nums[i] >= *u.begin())
u.insert(nums[i]);
else l.insert(nums[i]);

// Remove number out of the window
if (i >= k) {
if (nums[i-k] >= *u.begin())
u.erase(u.find(nums[i-k]));
else l.erase(l.find(nums[i-k]));
}

// Balance the size of two sets
while (u.size() < l.size()) {
u.insert(*l.rbegin());
l.erase(--l.end());
}
while (u.size() > l.size() + 1) {
l.insert(*u.begin());
u.erase(u.begin());
}

// Push back median
if (i >= k-1) {
if (k & 1) res.push_back(*u.begin());
else res.push_back(((double)*u.begin() + *l.rbegin()) / 2);
}
}
return res;
}
};``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.