The Top K frequent elements is one of the many problems in Leetcode that involve hashing, and is also one of the first Medium challenge found in Neetcode, specifically when you start at the Arrays & Hashing section in the roadmap.

It states that given an array of integers and an integer k, create a function that returns the k most frequent integers.

It sounds easy enough, but the Dunning-Kruger effect got me once again. So, I opened the Hints section. It told me that the ideal solution must be O(n), and an algorithm that involves sorting based on frequency is applied to it. Google then led me to the Bucket Sort Algorithm.

From my understanding, the Bucket Sort Algorithm is well, an algorithm that is used to partition an input array into smaller arrays, assigning an element into an element array (or in this case, buckets).

After lots of syntax error and wrong outputs, here is what I came up with.

First, I initialized the needed data structures, namely the map dictionary, the bucket array which is just an array of arrays, and the result array.

def topKFrequent(self, nums: List[int], k: int) -> List[int]:
    map:dict[int,int] = {}
    bucket:list[list[int]] = []
    result:list[int] = []

Enter fullscreen mode Exit fullscreen mode

Then, I used a for loop to populate the empty array into well, more empty arrays, specifically len(nums) + 1 of them in order to handle the edge case of the array going out of bounds when the frequency of an element is equal to the length of the array.

#Initialize bucket
for i in range(0, len(nums) + 1):
    bucket.append([])

Enter fullscreen mode Exit fullscreen mode

Next, in order to count the frequency of each integer,I utilized the map hashmap, where the integer serves as the key and its frequency as the value.

#Map the numbers to their frequency
for num in nums:
    if num in map:
        map[num] = map.get(num) + 1
    else:
        map[num] = 1

Enter fullscreen mode Exit fullscreen mode

After that, this is where the bucket sort algorithm is implemented. The frequency of the integer serves as the index to which bucket will the integer be appended. The more frequent an integer appears, the higher the index it will be assigned to.

#Use frequency as index when appending to an inner array
for num,freq in map.items():
    bucket[freq].append(num)

Enter fullscreen mode Exit fullscreen mode

Finally, I stored the most frequent integers into the result array, checking until a length of k is reached. Since the most frequent integers were indexed at the near-ends of the array, we must iterate backwards in order to access them first.

#Iterate backwards, insert numbers to result array until k length is reached
for arr in reversed(bucket):
    if arr == []:
        continue
    for nums in arr:
        result.append(nums)
        if len(result) == k:
            return result
return []

Enter fullscreen mode Exit fullscreen mode

And that's it. Overall, it took me around 30 minutes to solve the problem. I'm also still trying to study the behavior of Python data structures since I come from Java, so syntax errors at the very first press of Run will be inevitable xD.