# 7-line C++ O(N*logk) solution using multiset for sliding window (comments and detailed explanation)

• This is my minor changed version of @StefanPochmann 's multiset solution. Originally, I was using two iterators `L, R` for middle left and middle right positions of sliding window (`L==R` if `k` is odd), but using two iterators seems to be redundant.

Note:

• Iterator `m` is always pointing to the middle right position of sliding window, i.e., `m` is the `k/2`th value (zero-based).
• When the sliding window moves towards right for one position, `m` moves at most twice to re-position to the updated middle right position.
• Median value `med` of a sliding window is given by `med = *m/2. + *ml/2.` to handle possible overflow, where `ml` points to middle left postion, i.e., `(k-1)/2`th value in sliding window.
``````    vector<double> medianSlidingWindow(vector<int>& nums, int k)
{
multiset<int> w(nums.begin(), nums.begin()+k);   // first sliding window
auto m = next(w.begin(), k/2);                   // middle (right) position
vector<double> med = {*m/2.+*next(m,k%2-1)/2.};  // median array
for (auto i = nums.begin(); i < nums.end()-k; w.erase(w.lower_bound(*i++)), med.push_back(*m/2.+*next(m,k%2-1)/2.))
{
if (w.insert(*(i+k)), *(i+k) < *m) --m; // move to middle (left)
if (*i <= *m) ++m; // back to middle (right)
}
return med;
}
``````

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