Top K Frequent Elements — Bucket Sort Beats the Heap

Problem Statement#

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

Constraints:

• 1 <= nums.length <= 10^5
• -10^4 <= nums[i] <= 10^4
• k is in the range [1, the number of unique elements in the array].
• It is guaranteed that the answer is unique.

Example 1:
Input:  nums = [1, 1, 1, 2, 2, 3], k = 2
Output: [1, 2]
Explanation: '1' appears 3 times, '2' appears 2 times. Top 2: [1, 2].

Example 2:
Input:  nums = [1], k = 1
Output: [1]

Example 3:
Input:  nums = [4, 1, -1, 2, -1, 2, 3], k = 2
Output: [-1, 2]
Explanation: Both '-1' and '2' appear twice. Either order is valid.

Why This Problem Matters#

Top K Frequent Elements is a canonical "top K" problem that interviewers use to probe three levels of understanding: can you solve it at all (heap), can you optimize it (bucket sort), and can you articulate the trade-off between the two? Companies like Amazon and Google ask this because "find the top K items by frequency" is a real production task — finding the most common error codes in logs, the most purchased products in a session, or the most queried terms in a search system.

The heap approach (build a frequency map, then use a min-heap of size k) is well-known and should be your baseline. It runs in O(n log k) time, which is efficient when k is small. But the bucket sort approach unlocks O(n) time by exploiting a key constraint: the maximum possible frequency of any element is n (if all elements are the same). This means frequencies are bounded integers in [1, n], which is exactly the domain where bucket sort shines.

Recognizing when bucket sort is applicable is a valuable skill. Any time you are sorting by a bounded integer key — frequency, rank, distance — consider whether bucket sort can replace comparison-based sorting and drop the log factor from your complexity.

The problem also tests your ability to describe the relationship between frequency maps and sorted output. The heap extracts the top k elements from an unsorted frequency map using a priority queue. The bucket sort groups elements by frequency and then scans buckets from high to low. Both produce the same result, but bucket sort avoids any comparison-based sorting, making it asymptotically faster.

The Core Insight#

Step 1 — Build the frequency map. Count how many times each element appears. This takes O(n) time and O(n) space.

Step 2a (Heap approach) — Maintain a min-heap of size k. For each element in the frequency map, push it onto the heap. If the heap exceeds size k, pop the minimum. After all insertions, the heap contains the k most frequent elements. Cost: O(n log k).

Step 2b (Bucket sort approach) — Group by frequency. Create an array buckets of size n + 1 where buckets[freq] holds all elements with that frequency. Populate buckets in O(n). Then scan buckets from index n down to 1, collecting elements until you have k. Cost: O(n).

The bucket sort approach is optimal: O(n) time and O(n) space. The key insight is that frequency is bounded by n, so we can afford to create a bucket for every possible frequency value.

Visual Dry Run#

Input: nums = [1, 1, 1, 2, 2, 3], k = 2

Step 1 — Frequency map: freq = {1: 3, 2: 2, 3: 1}

Step 2 — Bucket sort (array of size n+1 = 7):

Step 3 — Scan from high to low, collect k=2 elements:

• Index 6: empty
• Index 5: empty
• Index 4: empty
• Index 3: [1] → collect 1. Count = 1.
• Index 2: [2] → collect 2. Count = 2 = k → done.

Result: [1, 2]

Heap approach trace on the same input:

Push (3, 1) to heap → heap: [(3, 1)] Push (2, 2) → heap: [(2, 2), (3, 1)] Push (1, 3) → heap size = 3 > k=2 → pop min (1, 3) → heap: [(2, 2), (3, 1)]

Extract values: [1, 2]

Solution (Optimal)#

from collections import Counter
 
def topKFrequent(nums: list[int], k: int) -> list[int]:
    # Step 1: Count frequencies
    freq = Counter(nums)
 
    # Step 2: Bucket sort — index is frequency, value is list of elements
    buckets = [[] for _ in range(len(nums) + 1)]
    for val, count in freq.items():
        buckets[count].append(val)
 
    # Step 3: Scan from highest frequency down, collect k elements
    result = []
    for i in range(len(buckets) - 1, 0, -1):
        result.extend(buckets[i])
        if len(result) >= k:
            return result[:k]
 
    return result  # Guaranteed to return within the loop
 
 
# Heap approach — O(n log k) — useful when memory for n buckets is a concern
import heapq
 
def topKFrequent_heap(nums: list[int], k: int) -> list[int]:
    freq = Counter(nums)
    # nlargest uses a min-heap of size k internally: O(n log k)
    return [val for val, _ in freq.most_common(k)]

var topKFrequent = function(nums, k) {
    // Step 1: Count frequencies
    const freq = new Map();
    for (const n of nums) {
        freq.set(n, (freq.get(n) || 0) + 1);
    }
 
    // Step 2: Bucket sort
    const buckets = Array.from({ length: nums.length + 1 }, () => []);
    for (const [val, count] of freq) {
        buckets[count].push(val);
    }
 
    // Step 3: Scan from high to low, collect k elements
    const result = [];
    for (let i = buckets.length - 1; i >= 1 && result.length < k; i--) {
        result.push(...buckets[i]);
    }
 
    return result.slice(0, k);
};

Complexity Analysis

The bucket sort approach is optimal at O(n) with O(n) space. The heap approach is excellent when k is small and memory for n buckets is a concern (e.g., very large n).

Common Mistakes#

• Not handling the case where multiple elements share the same bucket. When a bucket at index i has more than k - (already collected) elements, you must take all of them from that bucket before stopping (or trim at the end with result[:k]). The problem guarantees the answer is unique, so this edge case is eliminated for this specific problem, but it matters in the general pattern.
• Off-by-one when creating buckets. You need indices 0 through n inclusive, so the bucket array should have size n + 1. Using range(n) creates only indices 0 through n-1, losing the bucket for the highest possible frequency.
• Using Counter.most_common(k) without understanding why it works. Python's most_common(k) uses a heap internally and runs in O(n log k). Presenting this as "O(n)" is incorrect and will be challenged in interviews.
• Not accounting for negative numbers in the frequency map. Negative integers are valid elements and valid map keys. The frequency count is always non-negative, so the bucket index is always non-negative. Negative element values do not affect the bucket indices.
• Confusing element value with frequency. In the bucket sort, the index is the frequency and the stored value is the element, not the other way around.

Follow-up Questions#

What is the most space-efficient approach when k is much smaller than n? Use a min-heap of size k. Space is O(k) for the heap plus O(n) for the frequency map. The frequency map is unavoidable; the heap avoids the O(n) bucket array.

What if you need to find top-k by frequency in a stream? Maintain a frequency map that updates with each new element. For top-k queries, use a sorted data structure (balanced BST or heap) to extract the top k. This is the "heavy hitter" or "frequent items" problem in data streaming.

Can you solve this in O(n) time and O(1) extra space (excluding the output)? Not in general — you need at least O(n) space to store the frequency map. The O(1) space claim for bucket sort is incorrect; the bucket array itself uses O(n) space.

How does this problem relate to the "Kth Largest Element" family? Both involve finding a K-th or top-K item from a collection. The difference is the comparison key: here it is frequency, there it is value. The same data structures (heap, bucket sort, QuickSelect) apply to both.

What if the elements are strings, not integers? The frequency map still works. The bucket sort still works (bucket index = frequency, which is always an integer). The element type does not matter for the algorithm structure.

Key Takeaways#

• LC 347 Top K Frequent Elements is the canonical hashmap-plus-selection problem.
• Step 1 always: build a frequency Counter/Map in O(N).
• Bucket sort runs in O(N) by indexing buckets by frequency (1..N) — optimal when frequencies are bounded by N.
• Min-heap of size K runs in O(N log K) — better when K << N or memory matters.
• QuickSelect on (value, freq) pairs gives expected O(N) average and is great for "top-K" interview follow-ups.
• The bucket-sort approach beats the heap on raw runtime; the heap is more general (works for streams).
• Same frequency-then-rank pattern shows up in trending tweets, top-K logs, and analytics dashboards.

Related Problems#

• LC 347 — Top K Frequent Elements: This problem.
• LC 692 — Top K Frequent Words: Same idea but with string elements and lexicographic tie-breaking.
• LC 215 — Kth Largest Element in an Array: Find the k-th largest value (not frequency) — uses QuickSelect or a heap.
• LC 378 — Kth Smallest Element in a Sorted Matrix: K-th selection from a 2D structure.
• LC 973 — K Closest Points to Origin: Top-k by distance — same heap/bucket pattern.
• LC 767 — Reorganize String: Uses frequency counts to check if a valid rearrangement exists — related frequency reasoning.