Leetcode 347. Top K Frequent Elements

Problem

Leetcode 347 - Top K Frequent Elements

Example:

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

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

Approach

We can have freq HashMap to count how much each elements exists in array

We can use count array of array to put down the elements from freq HashMap where key represents number, and val represents the frequency of elements. Thus count[val] = key

We then finally iterate the count array from the end to beginning and append ‘k’ amount of numbers which will represent k most frequent elements

Visualization of the Approach:

nums = [1,1,1,2,2,3], k = 2
count = [[], [], [], [], [], [], []]
freq = {}

freq = {1: 3, 2: 2, 3: 1}
With this, we can add elements in count[val] = key where val represents the frequency of elements, and key is number

count = [[], [3], [2], [1], [], [], []]
With this we return the k top elements

Thus, res = [1, 2]

Here is the Python code for the solution:

class Solution:
    def topFrequent(self, nums: List[int], k: int) -> List[int]:
        count = [[] for _ in range(len(nums)+1)]
        freq = {}

        for num in nums:
            freq[num] = 1 + freq.get(num, 0)
        
        for key, val in freq.items():
            count[val].append(key)
        
        res = []
        for i in range(len(count)-1, -1, -1):
            for n in count[i]:
                res.append(n)
                if len(res) == k:
                    return res

Time Complexity and Space Complexity

Time Complexity: $O(n)$

Space Complexity: $O(n)$