We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
I see an implementation with counting sort and no queues but it's really complex. Like you need to keep track of the indices of the median(s) so when you update the counting array you know what the new median is in all cases. It seems way more complicated than an interview question should ask though.
I watched the video in the editorial. Using 2 priority queues will work but insertion, deletion, and swapping are O(log(n)) for heaps. Overall time complexity is O(nlogn). So it's not as performant as just using the counting array. Counting sort is o(n). It's not like 2 priority queues is an elegant solution with all the rebalancing needed.
Most solutions here are O(n^2) worst case (d is half of n)
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Fraudulent Activity Notifications
You are viewing a single comment's thread. Return to all comments →
I see an implementation with counting sort and no queues but it's really complex. Like you need to keep track of the indices of the median(s) so when you update the counting array you know what the new median is in all cases. It seems way more complicated than an interview question should ask though.
I watched the video in the editorial. Using 2 priority queues will work but insertion, deletion, and swapping are O(log(n)) for heaps. Overall time complexity is O(nlogn). So it's not as performant as just using the counting array. Counting sort is o(n). It's not like 2 priority queues is an elegant solution with all the rebalancing needed.
Most solutions here are O(n^2) worst case (d is half of n)