Top K Frequent Elements

───✱*.｡:｡✱*.:｡✧*.｡✰*.:｡✧*.｡:｡*.｡✱ ───

Problem

• 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.
• You may return the output in any order.

Solution

• We want to make a frequency count of the numbers in the list.
• Since grouping can replace sorting, we can do bucket sort.
  • The bucket index would be the frequency, and the values would be the numbers with the frequency (reverse of a typical bucket sort).
  • Then, scan backwards to get the most frequent.

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        # time complexity: O(n)
        # space complexity: O(n)
        freq = {}
 
        for num in nums:
            freq[num] = freq.get(num, 0) + 1
 
        buckets = [[] for _ in range(len(nums) + 1)]
 
        for num, count in freq.items():
            buckets[count].append(num)
 
        res = []
 
        for i in range(len(buckets) - 1, 0, -1):
            for num in buckets[i]:
                res.append(num)
                if len(res) == k:
                    return res
 
        return []

───✱*.｡:｡✱*.:｡✧*.｡✰*.:｡✧*.｡:｡*.｡✱ ───