Top K Frequent Elements (LeetCode 347) | Full solution with examples | Interview | Study Algorithms

Finding the top k frequent elements in an array is not similar to finding the top k students in a class. We need to understand the problem statement clearly, what it is expected. In this video we look at example test cases on how to determine the top k frequent elements efficiently using the bucket sort algorithm. All of this along with a dry-run of code in JAVA.

Chapters:
00:00 - Intro
01:06 - Problem statement and description
03:29 - How to approach the problem?
06:49 - Solving for efficiency
11:32 - Dry-run of Code
14:13 - Final Thoughts

📚 Links to topics I talk about in the video:

📖 Reference Books:

🎥 My Recording Gear:

💻 Get Social 💻

#interview #leetcode #algorithms

[helloworld]

@10:10 in the bucket 1, shouldn;t it be a 4

[jiwachhetri]

Didn't understand Neetcode so came here. This is very well explained. Instantly subscribed.

[rvbmoof]

Out of all the videos I watched over this problem, yours is the one I was able to truly understand. Thank you!

[satyamshukla]

Please dont stop teaching. Crystal Clear explaination bhaiya

[jonformantes]

I just found your channel. Both you & neetcode do amazing work. Thank you so much for these!

[kanishparihar]

It's certainly clever. But when k is small, and n is large, its wasteful of both time and space (or at least of time and memory allocations). When k == n, it's at least wasteful of space.

Essentially, it suffers from the same class of problem as bucket sort does. It's great when the data is evenly distributed. But can have some real drawbacks when the data is not. Unfortunately, for this problem, the data cannot be evenly distributed. Here's why:
Consider the case where n == k (or is very close), one of two "edge cases" are possible:
a) each element occurs once, so you have a bucket for every possible frequency between 0 and n, but the only frequency that gets used is 1. Because k cannot exceed n, if all elements are to be included then all must be of equal frequency, hence, only 1 of the buckets will get used.
b) there is only one element, and it occurs n times. Again, you will use only 1 bucket. The bucket for the "n" frequency. And again, the extra buckets are pointless.

Knowing this, we can see that it will never be possible to actually use all of the buckets, because there simply aren't enough locations in n for all the frequencies this approach accounts for.

I believe (although I don't feel like doing the math right this second), that the absolute best you could hope for would be that sqrt(n) buckets get used.

Now that we know that even if k == 1 and n is extremely large, we won't be able to use all the frequency buckets. k has no impact on that. In fact, the larger n becomes, the more "wasted" buckets there will be since the ratio of a value, v to its square decreases as v grows. The progression from 2 is 1/2, 1/3, 1/4, 1/5, 1/6, etc. So as n reaches max the number of buckets that will not be used is 1 - (1 / 63^n) assuming a 64 bit machine. And that's a lot of buckets.

As I said, same issues as bucket sort. Great if the data actually fills all the buckets. Unfortunately, given the constraints of this problem, you'll never fill all the buckets and I suspect that's why it wasn't included in the editorial.

Just want to say: We're splitting hairs here (as quite frankly, the most readable solution is a count with a sort and then taking a k sized slice and that's only barely slower than a heap in the worst case and about the same in the average case.) Quicksort and quickselect have always been complex. I've been doing this 25 years—I know no one who could implement either without a quick refresher and a little debugging. It was included in the editorial because its useful to know and understand. But in real life, you'd use an existing implementation.

[pushkarthakur]

i don't think the solution is going to be [1, 2, 3] since the loop is going to stop iterating as soon as counter becomes more than or equal to k, since k is equal to 2 and you are starting counter from 0, adding 1 at res[0] and then 2 at res[2] as soon as it get counter = 2, its gonna stop and the output will be [1, 2]

[sathiskumarp]

the problem is finding the top 2, so according to leetcode if we have two values with same frequency we should return only the first one

[simiiv]

Kya clear explanation hai. Thank you Nikhil !!!

[anudeepbilla]

12:45 I think you are reffering frequency values as keys which should ideally be values, if you see frequencies have 2 coming twice which should not be the case if they are keys which are meant to be unique

[kunalkheeva]

You are such a hardworking! appreciate your content.

[adityahpatel]

Great explanation of the logic. I am purely on python not java, but the way you explained this, i won't hv difficulty implementing it in python, since the logic is clear. Btw you've explained the logic better than neetcode

[khushichaurasia]

Great explanation u r amazing dude ❤😊keep it up

[KittyInCali]

superb explanation, thank you, I hope you have the leetcode blind 75 solutions

[fahimmimtiaz]

bhisaab kya samjhaya hai, ekdam goated bhai

[Hobbes]

How is this not O(n+k) because of the nested for loop?

[SachinKariyattin]

in the final example, the result array is defined as int[] res = new int[k] where k = 2. So only 2 elements can be added. However, the answer is [1, 2, 3]. Wont this throw index out of bounds for this example?

[ghanashrim]

Can you please make a video on 658. Find K Closest Elements too ?

[rilkedev]

Thank you for your extremely clear and concise video. Please rest assured that the YouTube algorithim will catch notice of your quality, and your channel will gain very quick and upward traction.

[mohammedilyas]

First view, first like, first comment