Top K Frequent Elements

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.

Approach

Count the frequency of each number with a hash map, then place numbers into buckets by frequency. The bucket array has indices 0..n, where each bucket i stores the numbers that appear i times. Walk the buckets from high to low, collecting numbers until k elements are gathered.

Why It Works

The frequency map records the exact occurrence count for each distinct number. By grouping numbers into buckets indexed by frequency and iterating from the highest frequency down, we retrieve elements in non-increasing frequency order. Since the answer is unique, the first k elements collected are the correct result.

Complexity

• Time: O(n)
• Space: O(n)

Reference Implementation (Python)

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        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)

        result = []
        for count in range(len(buckets) - 1, 0, -1):
            for num in buckets[count]:
                result.append(num)
                if len(result) == k:
                    return result
        return result