Click here to see the full article post
Add N words to the heap should take O(log N) time for each. So the complexity of approach 2 should also be O(log N)
The 2nd Python solution looks like O(Nlog(N)). You should use similar techniques such as heapreplace.
Why isn't the sorting O(k log k)? There are only k entries in the HashMap, so I think the sorting solution has time complexity of O(N + k log k), which is not necessarily slower than the heap solution of O(N log k).
@ryanleitaiwan Each push/pop has complexity O(log k) because there at most k items. However, N pushes are made.
@awice I understand the Heap Solution (N pushes, k pops), but I'm wondering about the Sorting Solution.
Actually, I misunderstood the notations. 1 ≤ k ≤ number of unique elements (call this U) ≤ N, then precisely speaking, the Sorting Solution has a time complexity of O(N + U log U). However, in average scenarios, we can expect 1 < k << U < N, so Heap should be faster.
I don't see how this ensures that words with same frequency are ranked in alphabetical order
@WhiterMeerkat Assuming you are talking about the heap:
In Java, the comparator is
(w1, w2) -> count.get(w1) != count.get(w2) ?
count.get(w1) - count.get(w2) :
In Python, it is sorting by
The bolded areas indicate when it is sorting by word in the case of ties.
@awice for the Python solution, isn't this
heap = [(-freq, word) for word, freq in count.items()]
word with priority
-freq into the heap?
I'm not sure how this is different from
h =  for (freq, word) in count.items(): heappush(h, (-freq, word))
which does not work.
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.