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))
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.
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).
@@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
Master Data Structures & Algorithms For FREE at AlgoMap.io!
I hardly ever comment on TH-cam, but I had to. Your second solution is unique compared to others I have seen online. Great work!
This is the best explanation I came across, thank you!
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))
I'm not sure you'd be allowed to use most_common in an interview 🤔
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.
Hi, could you please explain why it's O(nlogk) instead of O(klogn)? I don't know why, thank you!
The second solution is very creative, thanks for sharing!
I love these heap questions, there's some really interesting solutions
This 2nd solution is briliant
It's really cool
Fantastic!
Thank you for that !
Very welcome :)
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?
Good work. Keep going 👍🏼
2:12, wait, it should've been O(klogn) if we only consider the work of heap
please help , how come the second solution is not o(n2)
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).
how its o(n) ?we have inner loop
Because there isn't an inner loop?
@@guinea_horn second solution from line 15 to 19 should not it be o(n2) ?
@@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
We need more
heappy heap
Heap it up
most_common?