O(n log k) C++ using multiset and updating middle-iterator


  • 40

    Keep the window elements in a multiset and keep an iterator pointing to the middle value (to "index" k/2, to be precise). Thanks to @votrubac's solution and comments.

    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(window.lower_bound(nums[i-k]));
        }
    }

  • 1
    K

    Very smart using a iterator to remove a element instead of the value


  • 0
    Y

    So what's the time complexity of next() method?
    I think next() in multpleset is not a random-access iterator, thus it's complexity is nearly O(k), to index mid term.


  • 1

    @yomin But cplusplus.com says that it's linear in the parameter, so it should be constant in my case here, no?

    Edit: I just did an experiment. I changed my line to

            medians.push_back((double(*mid) + *next(next(next(mid, k%2 - 1), -(k%2 - 1)), k%2 - 1)) / 2);
    

    which triples the number of next calls. But that doesn't have a noticeable effect on the runtime, my the solution still gets accepted in about 100 ms (as before). And if I instead move my auto mid = next(window.begin(), k / 2); into the loop, that does make the solution much slower, it then gets accepted in about 550 ms.

    So looks like my next(mid, k%2 - 1) is indeed constant time and thus my solution O(n log k).


  • 0
    Y

    @StefanPochmann yeh, yeh... My mistake...auto mid = next(window.begin(), k / 2); this line of code is O(n), next(mid, k%2 - 1) this line of code is O(1)... I mixed them up....great solution!


  • 0
    S

    Same idea, vote for you!


  • 0
    S

    @yomin Agree, next of mid inside loop scan at most one step. I think it could also be done by using two multiple sets, simulate left maxheap and right minheap. in that way, there is no need to worry about iterator, but this makes the code complicate.


  • 1
    S

    I am curious if it is possible when erasing, iterator mid can be removed, and next time to access mid will incur error.


  • 0
    S

    How did you make the right decision of mid++ and mid--. It looks simple, but takes time to figure out.


  • 2

    @singku Like I said, I just keep it pointing to "index" k/2. So when I insert something before it (i.e., something smaller), my pointer then points at "index" k/2+1 and I'll have to subtract 1 to fix that. Similar for erasing. And no, there won't be an error, because I increase the iterator before erasing, which avoids erasing the element my iterator points to.


  • 0
    N

    @StefanPochmann Still not 100% follow the logic of mid-- and mid++. Don't you need to distinguish the odd's k and the even's k two cases?


  • 0

    @ncybmh99 I do distinguish odd and even k. Read my median-computation line again.


  • 0
    N

    @StefanPochmann I understand that you calculate the mean based on either odd k or even k.

    My question is: shouldn't you distinguish odd k an deven k when you update the mid iterator:

       // Insert nums[i].
        window.insert(nums[i]);
        if (nums[i] < *mid) // no need to distinguish odd k and even k to do "mid--"?
            mid--;

  • 0

    @ncybmh99 No I don't need to do that. What makes you think I might?


  • 0
    C

    What if nums[i]>*mid? Don't we need to process in that situation

    I only saw

            if (nums[i]<*mid){
                mid--;
            }

  • 0
    Y

    @coder2 We just need to mantain half of the window, Either smaller part or lager part. The author use smaller part, so need to judge whether num[i] < mid? your situation is to consider larger part.


  • 0

    @yomin Not sure what you mean. I maintain the whole window.

    @coder2 If I insert a larger element, it gets inserted at a larger position. So it doesn't change the position of the element mid points to. So mid still points at the correct element.


  • 0
    Y

    wow, this is brilliant, it is hard for me to make the code this clean.
    I tried to write my own after I thought I understand the idea, but keeps failing on cases, I guess it maybe needs an initial version and then make it this clean, so hard to get this clean the first time for me.


  • 0

    @yanzhan2 Well you can see in the discussion in the linked topic that I didn't directly write it like this, either, and that I had help from @votrubac :-). Btw, I had the basic idea (multiset and iterator pointing to the middle) when I first saw the problem, but thought it would get ugly and solved this problem in a different way. Then I saw @votrubac's solution which motivated me to try it myself. And when we ended up with the above solution, I was surprised myself about how nice it had ended up.


  • 0
    I

    @StefanPochmann Is there a java way to do the same?


Log in to reply
 

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