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.
It is being downvoted because the poster excitedly proclaimed that their solution is O(n), without understanding that the PriorityQueue data structure itself is handling the sorting in O(n log n) time.
Implementation note: this implementation provides O(log(n)) time for the enqueing and dequeing methods (offer, poll, remove() and add); linear time for the remove(Object) and contains(Object) methods; and constant time for the retrieval methods (peek, element, and size).
We enque and deque - an O(log n) operation - n times. Hence O(n log n).
cris_kgi’s implementation is fine as a solution to the hackerrank problem, but it is not O(n), and they did not find the free lunch.
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Luck Balance
You are viewing a single comment's thread. Return to all comments →
It is being downvoted because the poster excitedly proclaimed that their solution is O(n), without understanding that the PriorityQueue data structure itself is handling the sorting in O(n log n) time.
https://docs.oracle.com/javase/7/docs/api/java/util/PriorityQueue.html
We enque and deque - an O(log n) operation - n times. Hence O(n log n).
cris_kgi’s implementation is fine as a solution to the hackerrank problem, but it is not O(n), and they did not find the free lunch.