Top K Frequent Elements - Bucket Sort - Leetcode 347 - Python

0:00 - Read the problem
2:58 - Drawing Explanation
9:42 - Coding Explanation

leetcode 347

#sorted #array #python
Disclosure: Some of the links above may be affiliate links, from which I may earn a small commission.

[Xeoncross]

I appreciate the time you put making and sharing all your content for free. Here is the $10 I might have spent on your udemy course.

[rhitamdutta]

I have never practiced DSA in my life, not even in college. After getting laid off, I stumbled across your videos to learn DSA. They are so crisp, informative, and to the point. I can't thank you enough.

[tweefeety]

I love you man. You're an actual angel. Your explanations are always so clear. And your drawings are so easy to understand.

[rohananjaria]

Best youtube channel for leetcode problems hands down.

[justsimple]

i used your previous video on groupAnagrams to solve this, just hashmapped the array in to a defaultdict(int) den sorted the dictionary entirely in a descending order. Your videos have been really helpful, first time i solved a medium all by myself

[joshmarion]

Am I the only one who is a little confused as to how this solution is O(N). If you loop through the array which is the size of the array, and then in each index you might have to loop through up to N times. So how is this not o(n^2)

Edit: Nevermind, I think I realize it now, I figured I would write it out for anyone who might still be confused. As we traverse through the array, we go through the whole array. So this is O(n). But we aren't doing an operation n times at each stop. We are doing N more operation throughout the entire array. So even though the for loops are nested, we are doing N more operations throughout a for loop which is N, so the total is just N+N, which simplifies to O(N)

[sandeshpaudel]

for the heap solution, it's better to use a min heap of size k rather than using a max heap and then removing max k times. Using the min heap, you would remove min and add the next frequency. by the end, you are left with k most frequent ones and removing the min gives you the answer. You can reduce this to n log k and not n log n

[maierdanefan]

Amazing contents! The best algorithms channel that focus on logic and thinking in a clear way. Happy to have found this channel, been writing neetcode ever since.

[Number_Crunch]

The algorithm that you explained at 3:15 was counting sort and not bucket sort. What you did, however, towards the end was similar (not same as) bucket sort.

[leofastov]

I'd like to suggest a minor improvement:

for n in nums:
count[n] = 1 + count.get(n, 0)
if count.get(n, 0) > max_val:
max_val = count.get(n, 0)

freq = [[] for i in range(max_val + 1)]

The max_val variable is used to track the maximum frequency instead of using the length of nums.
This can potentially save some space if the maximum frequency is significantly less than the length of nums.

Addition of max_val adds a small const time overhead

[Thrashmetalman]

the one thing I dont like about usage of heap questions is that most of the times you havge to default to some library to do it cause I doubt any of us could code up a heap in a phone screen.

[HimanshuPant-cv]

this is how i did it, i basically converted the list in a dict, sorted it using values and the took out the k most frequent values but i really appreciate your videos.

class Solution:
from collections import Counter
def topKFrequent(self, nums: List[int], k: int) -> List[int]:
value = []
my_dict = dict(Counter(nums))
my_dict2 = dict(sorted(my_dict.items(), key=lambda item: item[1], reverse = True))
mlis = list(my_dict2.keys())
for i in range(k):
value.append(mlis[i])
return value

[andrepinto]

While counting, you can keep track of the max occurrences and then you only need to initialize freq to that max instead of len(nums)

[eulier]

That's was a very interesting way to solve a specific real life problems, by counting and working with hash and array as a way to identify K most frequent elements. This can be useful for small to big business handling inventory or when you need to pack-up your stuff to travel.

[wow_donnie]

I came up with this solution originally but really appreciated the thoughtful description of the linear solution!

result = defaultdict(int)
for num in nums:
result[num] += 1
result = dict(sorted(result.items(), key=lambda item: item[1]))
return list(result.keys())[-k:]

[netanelkaye]

People say you are supposed to learn enough to be able to figure out leetcode problems, as opposed to memorizing leetcode. Are we seriously supposed to have been figured this method out? This was so specific...

[VineetKrGupta]

I got my first job after following your neetcode 150, 2 years ago. now after the layoff i am here again learning the dsa.

[awesome_ashu]

We can optimize it more by storing the maxFrequency while creating the HashMap (which has the integer and their corresponding frequency). Then, the next iteration to get the required elements can start from this maxFrequency instead of N.

[md-ayaz]

One thing to note in python. Please do not intialize like this ( if you are )
bucket = [[]] * (len(nums) + 1)
this references to the same list and your output will be wrong.

Use the bucket = [[] for _ in range(len(nums)+ 1)], as mentioned in the video.

[johnzheng]

Your video got a me a job as an SDE at AWS!!