Overview
I walk you through how to solve Leetcode problem 347. Top K Frequent Elements.
Approach 1: Count HashMap
def topKFrequent(nums, k):
count = {}
res = []
for n in nums:
count[n] = count.get(n, 0) + 1
for _ in range(k):
tmax = max(count, key = count.get)
res.append(tmax)
count.pop(tmax)
return res
In this first approach, we create a count HashMap and a res array to begin. We then iterate through each number in our input array nums and map the number to its count respectively.
Next, we go through k iterations and get the number with the maximum count value. This is done using the max function with the key set to the .get function. In short, this passes the values returned from the .get method to be calculated in the max function.
Once we get this max, we append it to our res list and pop the number out of our HashMap. After the iteration is complete, we return the res list.
Time Complexity: Worst - O(N²) / Avg - O(N Log N)
The time complexity of the function is O(N log N) in the average case and O(N²) in the worst case. This worst-case scenario occurs when all the elements in nums are unique and k is equal to the length of the list nums. In this case, the second loop needs to find the maximum value k times with the max function taking O(N) time in the worst case, and then remove it from the count dictionary. Therefore, the total time complexity becomes O(N²).
However, in most cases, the number of unique elements in nums is much smaller than n, and k is also much smaller than n. Therefore, the average case time complexity of the function is O(N log N), which is the result of sorting the dictionary count by its values.