roadmap/arrays-hashing/Top K Frequent Elements

Top K Frequent Elements

MediumAmazonGoogleFacebookBloomberg

Problem

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

Intuition — the key insight

The trick is bucket sort. Frequencies range from 1 to n. Create n+1 buckets where bucket[i] contains all numbers that appear exactly i times. Then scan from the highest frequency bucket down to collect k elements — guaranteed O(n).

Approach

1. Count frequencies

Use a HashMap to count how many times each number appears.

2. Bucket sort by frequency

Create an array of buckets indexed by frequency (1 to n). Place each number in its frequency bucket. Scan from high to low frequency, collecting results until we have k elements.

Complexity

Time

O(n)

Space

O(n)

Counting is O(n). Bucket creation is O(n). Scan is O(n). Total O(n) — better than heap approach's O(n log k).

Solution code

Python

def topKFrequent(self, nums: List[int], k: int) -> List[int]:
    count = Counter(nums)
    
    # Bucket: index = frequency, value = list of numbers
    buckets = [[] for _ in range(len(nums) + 1)]
    for num, freq in count.items():
        buckets[freq].append(num)
    
    result = []
    for i in range(len(buckets) - 1, 0, -1):
        result.extend(buckets[i])
        if len(result) >= k:
            return result[:k]
    return result

Edge cases to remember

⚠k equals number of unique elements (return all)

⚠All elements the same frequency

⚠k = 1 (most frequent)

Hints

What pattern do you think this problem uses?