347. Top K Frequent Elements

Given an integer array nums and an integer k, return the k most frequent elements. You may return the answer in any order.

Solution

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        freq = defaultdict(int)
        for num in nums:
            freq[num] += 1

        buckets = [[] for i in range(len(nums)+1)]
        for num, occurences in freq.items():
            buckets[occurences].append(num)
        
        ret = []
        for idx in range(len(nums), 0, -1): #start-incl,stop-nincl,step
            for num in buckets[idx]:
                ret.append(num)
                if len(ret) == k:
                    return ret

Time Complexity: O(n)

Space Complexity: O(n)

Explanation

The idea is to first form a dictionary of the numbers and their frequencies. Then from this dictionary we must pull out the k most frequent numbers

There are two approaches. You could pull out the items and sort them by their frequency (nlgn), or you can place them in buckets by their frequency, (n).