LeetCode Top K Frequent Elements: Heap and Bucket Sort

Intermediate 9 min read

What you'll learn

✓How to use a min-heap of size k for top-K problems
✓Why bucket sort drops this to O(n) when frequencies are bounded by n
✓Counting with a hash map cleanly
✓When to pick heap vs bucket in interviews
✓Common edge cases and tie-breaking notes

Prerequisites

•Comfort with [hash maps](/blog/hashing-and-hash-maps)
•A sense of [Big-O analysis](/blog/big-o-notation-explained)

Top K Frequent Elements (LeetCode 347, Medium) shows up in product analytics and is a classic “two valid approaches” interview question. You can solve it with a min-heap in O(n log k) or with bucket sort in O(n).

The Problem

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

Example:

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

Brute Force

Count frequencies, sort by count, take the top k.

from collections import Counter

def top_k_brute(nums, k):
    counts = Counter(nums)
    return [x for x, _ in counts.most_common(k)]

O(n log n) because of the sort. most_common is convenient but not optimal.

Optimal Solution

Two clean optimal approaches.

Heap (O(n log k)):

import heapq
from collections import Counter

def top_k_heap(nums, k):
    counts = Counter(nums)
    heap = []
    for num, freq in counts.items():
        heapq.heappush(heap, (freq, num))
        if len(heap) > k:
            heapq.heappop(heap)
    return [num for _, num in heap]

Bucket sort (O(n)):

from collections import Counter

def top_k_buckets(nums, k):
    counts = Counter(nums)
    buckets = [[] for _ in range(len(nums) + 1)]
    for num, freq in counts.items():
        buckets[freq].append(num)
    result = []
    for freq in range(len(buckets) - 1, 0, -1):
        for num in buckets[freq]:
            result.append(num)
            if len(result) == k:
                return result
    return result

Bucket sort works because frequency is bounded by len(nums).

Walk Through an Example

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

Counts: 1 -> 3, 2 -> 2, 3 -> 1.
Buckets index by frequency: index 1 has [3], index 2 has [2], index 3 has [1].
Walk from highest frequency down: pick 1 then 2. Stop at k.

Result: [1, 2].

Edge Cases

k equals number of distinct elements: return all of them.
Empty array with k = 0: return an empty list.
All elements equal: one bucket, return that single element.
Negative numbers: counters and heaps handle them identically.
Ties: the problem allows any valid ordering; both implementations are fine.

Complexity Analysis

Sort-based brute force: O(n log n) time, O(n) space.
Heap: O(n log k) time, O(n + k) space.
Bucket sort: O(n) time, O(n) space.

For small k, heap is great. For very large k, bucket sort wins.

How to Explain It in an Interview

Start by noting that frequencies are integers between 1 and n. That observation unlocks bucket sort. Walk through both. State the trade-off: heap is more general because it doesn’t depend on the bound on frequency; bucket sort is faster but assumes that bound. Most interviewers love when you mention both and pick the right one based on constraints. Then code the one you’re asked for, narrating invariants like “the heap always holds the current top-k candidates by frequency.”

LeetCode 692 Top K Frequent Words
LeetCode 215 Kth Largest Element in an Array
LeetCode 451 Sort Characters By Frequency
LeetCode 973 K Closest Points to Origin

Wrap up

Top K Frequent Elements is one of those problems where the optimal solution depends on input structure. Knowing that frequency is bounded by n is the kind of observation that separates senior candidates. Practice both implementations and explain why you chose which one.