Top K Frequent Elements — LeetCode 347 Heap and Bucket Sort

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, number of unique elements]
• It is guaranteed the answer is unique

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

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

Why This Problem Matters#

LeetCode 347 Top K Frequent Elements is asked in nearly every Meta and Amazon onsite. It tests four skills at once: hashing, heaps, sorting tradeoffs, and the willingness to beat O(n log k) with bucket sort when frequencies are bounded.

The follow-up "can you do better than O(n log n)?" is the real signal. Strong candidates jump from "I'd use a heap" to "actually, since frequency is bounded by N, bucket sort gives O(n)." That progression separates middle from senior.

Keywords: "top K frequent interview", "bucket sort heap", "FAANG frequency problem", "hash + heap".

The Core Insight#

Step 1: count frequencies with a hash map — O(n). Step 2: pick the K highest counts. Two ways:

• Heap: min-heap of size K on (count, value). O(n log k).
• Bucket sort: array indexed by count, scan from high to low. O(n).

Bucket sort wins because frequency is at most N. We are using counts as bucket indices.

Visual Dry Run#

nums = [1, 1, 1, 2, 2, 3], k = 2.

Solution (Bucket Sort — Optimal)#

from collections import Counter
 
class Solution:
    def topKFrequent(self, nums, k):
        cnt = Counter(nums)
        buckets = [[] for _ in range(len(nums) + 1)]
        for v, c in cnt.items():
            buckets[c].append(v)
        out = []
        for i in range(len(buckets) - 1, 0, -1):
            for v in buckets[i]:
                out.append(v)
                if len(out) == k:
                    return out
        return out

var topKFrequent = function(nums, k) {
    const cnt = new Map();
    for (const v of nums) cnt.set(v, (cnt.get(v) || 0) + 1);
    const buckets = Array.from({length: nums.length + 1}, () => []);
    for (const [v, c] of cnt) buckets[c].push(v);
    const out = [];
    for (let i = buckets.length - 1; i > 0 && out.length < k; i--) {
        for (const v of buckets[i]) {
            out.push(v);
            if (out.length === k) return out;
        }
    }
    return out;
};

Time: O(n) — count + bucket build + linear scan. Space: O(n) — counter + buckets.

Solution (Heap)#

import heapq
from collections import Counter
 
class Solution:
    def topKFrequentHeap(self, nums, k):
        cnt = Counter(nums)
        h = []
        for v, c in cnt.items():
            heapq.heappush(h, (c, v))
            if len(h) > k:
                heapq.heappop(h)
        return [v for _, v in h]

Time: O(n log k). Space: O(n + k).

Common Mistakes#

• Sorting the entire frequency map — O(n log n), suboptimal.
• Using a max-heap of size N — works but worse than min-heap of size K.
• Forgetting that bucket index 0 is unused (no element has count 0).
• Not handling ties — problem guarantees uniqueness, but in real interviews, ask.
• Returning counts instead of values.

Interview Tips#

• Lead with the heap, then upgrade to bucket sort.
• State that frequency is bounded by N — that is what enables bucket sort.
• Mention that the order does not matter (per problem statement).
• For very large K, both approaches converge to O(n log n) anyway.

Follow-up Questions#

• What about Top K Frequent Words (LC 692)? Add lexicographic tie-break.
• Streaming? Heap of size K on (count, value), update on increment.
• Distributed? Each shard returns top K; merge with K-way heap.
• Approximate top K at scale? Count-Min Sketch + heap (Misra-Gries).

Key Takeaways#

• LeetCode 347 has two optimal approaches: O(n log k) heap and O(n) bucket sort.
• Frequency is bounded by N, which enables bucket sort.
• Step 1 is always: build a frequency hash map.
• Heap of size K with min-heap on (count, value) is the safe interview default.
• Bucket sort wins when interviewers push for "better than O(n log n)".
• Order of the returned array does not matter for LC 347.
• For words (LC 692), add lexicographic tie-breaking.