Help me out in this problem

#1

can there is a better solution from my code


q link

#2

@mr.encoder are u there bro?

#3

Yes, i was seeing your code.
I can see the approach you have used is ideal and the submission has been accepted. The concept of multiset is ideal, the submission is faster than 17.14% of C++ online submissions for Sliding Window Median because most of the submissions have been made by using this algorithm only. As per me, your using multiset approach your code is perfect :smile:

#4

Moreover i would also suggest you to read this documentation .
an approach to solving the problem using a Policy-based Ordered set data structure.
Follow the steps below to solve the problem:

  1. Insert the first window of size K in the Ordered_set( maintains a sorted order). Hence, the middle element of this Ordered set is the required median of the corresponding window.
  2. The middle element can be obtained by the find_by_order() method in O(logN) computational complexiy.
  3. Proceed to the following windows by remove the first element of the previous window and insert the new element. To remove any element from the set, find the order of the element in the Ordered_Set using order_by_key() , which fetches the result in O(logN) computational complexity, and erase() that element by searching its obtained order in the Ordered_Set using find_by_order() method. Now add the new element for the new window.
  4. Repeat the above steps for each window and print the respective medians.
#5

@mr.encoder can you provide me code of above policy based approach

#6

The code you have implemented is exactly the same as required, you just haven’t used c++ stl for that i would suggest you to see that documentation here
http://www.cplusplus.com/reference/set/multiset/
As if i would provide you with the code, you won’t be able to understand it so i would prefer you to optimize your own solution.

#7

@mr.encoder okay bro

#8

Still if you want you can refer it here https://www.geeksforgeeks.org/median-of-sliding-window-in-an-array-set-2/
As they have implemented with good explanation.

#9

@mr.encoder it is nice thank you

#10

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.

#11

hi @shivammishra20121999
u have reopened the doubt… is there still anything??
i think @mr.encoder has very well answered ur query…

#12

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.