Top K Frequent Elements — When HashMaps Start Earning Their Salary

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.

Example 1:

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

Output: [2,3]

Example 2:

Input: nums = [7,7], k = 1

Output: [7]

Constraints:

• 1 <= nums.length <= 10^4.

• -1000 <= nums[i] <= 1000

• 1 <= k <= number of distinct elements in nums.

My Thought Process

Step 1:
Count frequencies. That’s obvious.

Step 2:
Sort elements based on frequency.

Step 3:
Take the top k.

That’s it.

• Use a dictionary to store frequencies.

• Loop through nums and count occurrences.

• Sort keys based on their frequency (descending).

• Pick the first k.

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        hs = defaultdict(list)
        ans = []
        for i,num in enumerate(nums):
            if num in hs:
                hs[num] += 1
            else:
                hs[num] = 1
        for key in sorted(hs, key=hs.get, reverse=True):
            if(k>0):
                ans.append(key)
                k -= 1
        return ans

What surprised me was that even with an extra HashMap and a sorting step, this implementation still performed better than most submissions.