LeetCode 347 Top K Frequent Elements - Example and Complexity Analysis

Trace through nums = [3, 0, 1, 0] with k = 1.

Count frequencies: {3: 1, 0: 2, 1: 1}.

Create buckets of size $n + 1 = 5$:

• Bucket 1: [3, 1] (elements appearing once)
• Bucket 2: [0] (elements appearing twice)
• Buckets 0, 3, 4: empty

Scan from highest bucket (index $4$) down. Bucket 4: empty. Bucket 3: empty. Bucket 2: found [0]. You need k = 1 element, so return [0].

Counting takes $O(n)$. Building buckets takes $O(n)$. Scanning buckets takes $O(n)$ in the worst case. Total: $O(n)$ time.

The hash map and bucket array each use $O(n)$ space.