Problem statement

Statement

Given an integer array nums and an integer k, return the k most frequent elements. The answer can be returned in any order.

Examples

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

nums = [1], k = 1
→ [1]

nums = [4, 1, -1, 2, -1, 2, 3], k = 2
→ [-1, 2]   (both appear twice)

Constraints

1 ≤ len(nums) ≤ 10⁵
-10⁴ ≤ nums[i] ≤ 10⁴
k is in the range [1, number of distinct values].
Solve in better than O(n log n). Sorting is the obvious answer; the interview is checking whether you can beat it.

What this problem is really testing

Whether you reach for the right complexity. The naive sort is O(n log n); the canonical heap solution is O(n log k); the bucket-sort solution is O(n). Three approaches, each better than the last. The problem is small but the spread of "good enough" to "optimal" is large, and interviewers use it to see how far you push.

Hints

Count first. A hash map (or Counter) maps each value to its frequency in O(n).
The naïve next step. Sort the (value, count) pairs by count, take the first K. O(n log n): it works, but it doesn't earn the question.
Heap improvement. Maintain a min-heap of size K. For each (value, count), push; if the heap exceeds size K, pop the smallest. At the end the heap contains the top K. Time: O(n log k). Memory: O(n + k).
The bucket-sort insight. Each value's frequency is between 1 and n. So we can place each value in a bucket indexed by its frequency. After all values are placed, walk buckets from highest index down; the first K values you collect are the answer.
Why bucket sort works here. Frequencies are bounded by n, so the bucket array is O(n). Walking it is O(n). Total: O(n), strictly better than the heap version.
When NOT to use bucket sort. If the score range is unbounded or much larger than n (e.g., real-valued scores in [0, 1]), bucket sort is impractical. Heap is the right answer in that case.

Solution and approaches

Solution: three approaches

Approach 1 · Sort + slice: O(n log n) time, O(n) space

The reflex answer. Count frequencies, sort the items by frequency, take the first K.

from collections import Counter

def top_k_frequent_sort(nums, k):
    freq = Counter(nums)
    return [val for val, _ in freq.most_common(k)]

most_common(k) internally uses a heap when k is small relative to the number of distinct values, so this is closer to O(n log k) in practice. Still, it's the version most people write first; it works but doesn't show the interviewer anything beyond "I know Counter."

Approach 2 · Min-heap of size K: O(n log k) time, O(n + k) space

The first real optimisation. Iterate the frequency map; maintain a min-heap of (count, value) pairs of size at most K. The smallest count in the heap is the threshold; if a new pair beats it, replace.

import heapq
from collections import Counter

def top_k_frequent_heap(nums, k):
    freq = Counter(nums)
    heap = []
    for val, cnt in freq.items():
        if len(heap) < k:
            heapq.heappush(heap, (cnt, val))
        elif cnt > heap[0][0]:
            heapq.heapreplace(heap, (cnt, val))
    return [val for _, val in heap]

Each push/replace is O(log k); we do at most n of them. Total: O(n log k). When K is much smaller than n, this is significantly better than the sort.

Why not a max-heap? A max-heap would let us pop the K largest in O(k log n). But Python's heapq is a min-heap, and using a min-heap of size K with the "pop on overflow" pattern is the standard idiom. Either approach has the same asymptotic.

Approach 3 · Bucket sort: O(n) time, O(n) space

The optimal answer. Counts are bounded by n, so we can bucket values by their count and walk back to front.

from collections import Counter

def top_k_frequent(nums, k):
    freq = Counter(nums)
    buckets = [[] for _ in range(len(nums) + 1)]
    for val, cnt in freq.items():
        buckets[cnt].append(val)
    out = []
    for i in range(len(buckets) - 1, 0, -1):       # high to low
        out.extend(buckets[i])
        if len(out) >= k:
            return out[:k]
    return out                                     # all values requested

Why len(nums) + 1 buckets: any value can appear at most n times. The "+ 1" gives index n for the maximum case; the "+ 0" bucket is unused (values with frequency 0 aren't in the counter at all).

Why walk back to front: the highest-frequency values live in the high-index buckets. Walking from n down to 1 visits them in descending order of frequency.

Why this is O(n): counting is O(n); bucket placement is O(distinct) ≤ O(n); the walk is O(n) in total even if we visit every bucket. No sorting; no log factor.

Complexity comparison

Approach	Time	Space	When to use
Sort	O(n log n)	O(n)	Reflex answer; works but unimpressive
Min-heap	O(n log k)	O(n + k)	K much smaller than n; bounded score range not available
Bucket sort	O(n)	O(n)	Score is bounded and roughly the size of the input

Edge cases to verify

k equals the number of distinct values. All distinct values are returned. The bucket walk collects everything before the early-exit triggers.
All values identical. One bucket at index n with one value; the answer is [value].
Negative values. Counter handles negatives transparently; no issue.
k = 1. Returns the single most frequent value. The walk's early-exit fires at the first bucket with anything in it.
Ties at the K-th position. Multiple values share the same frequency. The problem allows any valid answer; both heap and bucket-sort approaches return one consistent ordering. Interviewers usually don't probe this.

Common mistakes

Where beginners go wrong

Stopping at the heap solution. O(n log k) is good, but the bucket-sort O(n) is strictly better when the score range is bounded, which it is here. Interviewers asking this problem usually want to see you reach the linear-time answer.
Using a max-heap of size n. "Push everything, pop K times" is O(n log n + k log n), which is no better than sorting. The trick of a min-heap capped at K saves the log factor.
Off-by-one on the bucket array's size. The maximum frequency is n, so the array needs indices 0 through n (total length n + 1). Allocating just n indices crashes when a single value dominates the array.
Sorting the buckets. Each bucket holds values that all share the same frequency; their internal order doesn't affect the answer. Don't sort within buckets; it's wasted work.
Returning out directly without slicing. The final bucket can contain more than K values combined with earlier buckets. out[:k] trims to exactly K; out alone over-returns.

Interview follow-ups to expect

"Solve it for a stream: values arrive one at a time, return the top K so far at any moment." Maintain a frequency map plus a min-heap of size K, both incrementally updated. Each insert is O(log k). The bucket-sort approach doesn't fit a stream because it requires knowing the maximum frequency upfront.
"What if the array is too large to fit in memory?" Count-Min Sketch (a probabilistic frequency-counting structure) gives approximate frequencies in sub-linear memory, with bounded error. Top-K becomes approximate, which is usually fine for analytics.
"Top K by score, where scores can be fractional." Bucket sort no longer applies. Heap is the right answer; O(n log k) is optimal for unbounded scores.
"Top K most-recently-used elements." Switch from a frequency map to an LRU cache backed by a doubly linked list; see the LRU concept.
"What if K = ⌊n/2⌋, exactly half the values?" Bucket sort still O(n). Heap-of-K is O(n log n), the same as a full sort. The bucket approach wins decisively.

Top K Frequent Elements

Problem statement

Statement

Examples

Constraints

What this problem is really testing

Hints

Hints

Solution and approaches

Solution: three approaches

Approach 1 · Sort + slice: O(n log n) time, O(n) space

Approach 2 · Min-heap of size K: O(n log k) time, O(n + k) space

Approach 3 · Bucket sort: O(n) time, O(n) space

Complexity comparison

Edge cases to verify

Common mistakes

Where beginners go wrong

Interview follow-ups to expect

Related reading