TopK Elements

All credits to the question go to Neetcode.io. I am merely borrowing from him.

Link - Neetcode 150

Given an integer array nums and an integer k, return the k most frequent elements within the array.

The test cases are generated such that the answer is always unique.

You may return the output in any order.

Example 1:

Input: nums = [1,2,2,3,3,3], k = 2

Output: [2,3]

Approach 1

Pseudocode

Create empty hashmap
For each number in the list:
    get count and add to hashmap as (num, count)

Create an empty list of lists where the index serves as the frequency/count of the number
Add the nums from the hashmap to the the indexes based on their counts

Check that until you get the topK elements, iterate over every index and get the first element.

Code

nums=[]
k = 2
res = list()
hashmap = dict()
for val in nums:
    hashmap[val] = hashmap.get(val, 0) + 1

arr = [[] for _ in range(len(nums)+1)]
for key,v in hashmap.items():
    arr[v].append(key)
    
i = -1
while k>0:
    if arr[i]:
        res.append(arr[i][0])
        k-=1            
    i-=1
    

print(res)

Mostly correct on this approach except the last part - like WHAT THE FUCK?! The question clearly says to include the top-k frequent elements but here you are taking only the first element from each bucket LUL

That leads us to our next approach

Approach 2

Create empty hashmap
For each number in the list:
    get count and add to hashmap as (num, count)

Create an empty list of lists where the index serves as the frequency/count of the number
Add the nums from the hashmap to the the indexes based on their counts

Check that until you get the topK elements, iterate over every index and get all elements until you have hit the limit of K.

Code

res = list()
hashmap = dict()
for val in nums:
    hashmap[val] = hashmap.get(val, 0) + 1

arr = [[] for _ in range(len(nums)+1)]

for val,freq in hashmap.items():
    arr[freq].append(val)

i = len(arr)-1

while i>0:
    for num in arr[i]:
        res.append(num)
        if len(res) == k:
            return res
    i-=1

return res

There ya go, much cleaner and inline with what the question demands. This code also fixes a big issue with the logic that existed previously - if k is greater than the number of elements present, then it would fail because i would go beyond 0. Here, the minute we hit k, we just yeet out of the code so no such issues here.