Top K Frequent Elements - Leetcode 347 - Heaps (Python)

[@GregHogg]

Master Data Structures & Algorithms For FREE at AlgoMap.io!

[@johnboamah9510]

I hardly ever comment on KZbin, but I had to. Your second solution is unique compared to others I have seen online. Great work!

[@Banana-Joanne]

very grateful for your solution. admittedly, I'm not too familiar with heaps and bucket sort, so they both really went over my head. but I will keep on researching. Thanks for the good work.

[@alibaba888]

This is the best explanation I came across, thank you!

[@JoeTan-nq4fq]

Since we are already using Counter class, we can use most_common() method. counter = Counter(nums) top_k = counter.most_common(k) return list(map(lambda x: x[0], top_k))

[@0xDomain]

I'm not sure you'd be allowed to use most_common in an interview 🤔

[@rahuldwivedi4758]

Great work. But if you switch context in the middle, please make sure to complete the context. At 4:32 you were talking about max_heap and in that process it seemed you were explaining the time complexity would be O(Nlogk) but it actually was for min_heap.

[@jiasubaowenke]

Hi, could you please explain why it's O(nlogk) instead of O(klogn)? I don't know why, thank you!

[@AryanShetty-d6b]

@@jiasubaowenke becuse min heap will contain only k times elemnt others will e poped out

[@venzdrop]

from collections import Counter class Solution: def topKFrequent(self, nums: List[int], k: int) -> List[int]: f = Counter(nums) return [x[0] for x in f.most_common(k)]

[@christianjt7018]

The second solution is very creative, thanks for sharing!

[@GregHogg]

I love these heap questions, there's some really interesting solutions

[@Flybot20]

Good work. Keep going 👍🏼

[@jiasubaowenke]

Thank you so much! I have a question that why don't we just use couter.most_common in the heap solution, is it slower than the heap sort?

[@LearningWorldChatGPT]

Fantastic! Thank you for that !

[@GregHogg]

Very welcome :)

[@samspeaks-hk1vp]

please help , how come the second solution is not o(n2)

[@johnboamah9510]

The loop that fills the bucket array runs in O(n), where n is the length of nums. The loop that retrieves the top k elements iterates over the bucket array (size of n + 1) with O(n). Both loops are O(n), so the overall time complexity is O(n) not o(n^2).

[@fadygamilmahrousmasoud5863]

This 2nd solution is briliant

[@GregHogg]

It's really cool

[@n.h.son1902]

2:12, wait, it should've been O(klogn) if we only consider the work of heap

[@samspeaks-hk1vp]

how its o(n) ?we have inner loop

[@guinea_horn]

Because there isn't an inner loop?

[@samspeaks-hk1vp]

@@guinea_horn second solution from line 15 to 19 should not it be o(n2) ?

[@guinea_horn]

​@@samspeaks-hk1vpno, and I'm not sure why you think it is. Unless by n2 you mean 2*n rather than n^2, because we do have two iterations over n items but not an n^2 loop. 2*n reduces to O(n) in typical big o notation

[@richardpro8927]

We need more

[@cmarquay]

heappy heap

[@GregHogg]

Heap it up

[@rattlik1]

most_common?