# O(nlogk) C++ Multiset with Mid-Iterator Further Thought

• StefanPochmann's solution is great. His solution maintains the mid-iterator by the smaller half. Thus I want to try to maintain the mid-iterator with the larger half. And this turned out to be non-trival and I gained a lot from thinking about it, so I post my mirroring solution here along with my respect. The key points are:

1. maintain the invariant: guarantee the mid-iterator movement happens on the correct situation.
For smaller half solution it means mid-- when inserting `nums[i] < *mid` and mid++ when removing`nums[i-k] <= *mid`; for larger half solution it means mid++ when inserting `nums[i] >= *mid` and mid-- when removing `nums[i-k] >= *mid`, thanks to point 2.
2. The C++ 11 standard: newly inserted elements follow their equivalents already in the container. *This makes operating on the smaller half easier.
3. lower_bound and upper_bound semantic
``````class Solution {
public:
vector<double> medianSlidingWindow(vector<int>& nums, int k) {
multiset<int> window(nums.begin(), nums.begin() + k);
auto mid = next(window.begin(), k / 2);
vector<double> medians;
for (int i=k; ; i++) {
// Push the current median.
medians.push_back((double(*mid) + *prev(mid, 1 - k%2)) / 2);

// If all done, return.
if (i == nums.size())
return medians;

// Insert nums[i].
window.insert(nums[i]);
if (nums[i] >= *mid)
mid++;

// Erase nums[i-k].
if (nums[i-k] >= *mid)
mid--;
window.erase(prev(window.upper_bound(nums[i-k]),1));
}
}
};
``````

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