Top K Frequent Elements

Problem

Given an integer array nums and an integer k, return the k values that occur most often in nums. The answer may be returned in any order, and it is guaranteed to be unique (no ties that would make the choice ambiguous).

Follow-up: your algorithm should beat O(n log n) — i.e. do better than “sort everything by frequency”.

Examples

Example 1: nums = [1, 1, 1, 2, 2, 3], k = 2 → [1, 2] 1 appears three times and 2 twice; 3 appears once and is excluded.

Example 2: nums = [1], k = 1 → [1] Only one distinct value.

Example 3: nums = [4, 4, 4, 5, 5, 6], k = 1 → [4] 4 is the unique most frequent element.

Constraints

• 1 <= nums.length <= 10^5
• -10^4 <= nums[i] <= 10^4
• k is between 1 and the number of distinct elements; the answer is unique.

With n up to 10^5, counting is cheap; the challenge is selecting the top k without a full O(n log n) sort.

Think about it first

TL;DR

Count with a hash map, then bucket-by-frequency — O(n) time, O(n) space (heap variant: O(n log k)).

Approach 1 — Brute force (count, then sort all by frequency)

Tally frequencies with a hash map, sort every distinct value by its count, and take the top k.

from typing import List
from collections import Counter


def topKFrequent(nums: List[int], k: int) -> List[int]:
    count = Counter(nums)
    ranked = sorted(count, key=lambda v: count[v], reverse=True)
    return ranked[:k]

Complexity: O(n) to count + O(d log d) to sort d distinct values — O(n log n) worst case, O(n) space. It passes at n = 10^5, but it fully ranks all d values when only the top k are wanted — exactly what the follow-up says to beat.

Approach 2 — Min-heap of size k

To keep the k largest frequencies, you never need more than k candidates at once. A min-heap (a binary heap where the smallest element sits at the root, with O(log size) push/pop) of size k holds the current best k; any newcomer beating the root evicts it. Each of the d distinct values costs O(log k), not O(log d).

from typing import List
from collections import Counter
import heapq


def topKFrequent(nums: List[int], k: int) -> List[int]:
    count = Counter(nums)
    heap: List[tuple[int, int]] = []      # (frequency, value), min at root
    for value, freq in count.items():
        heapq.heappush(heap, (freq, value))
        if len(heap) > k:
            heapq.heappop(heap)           # evict current smallest
    return [value for _, value in heap]

Walkthrough on Example 1, nums = [1,1,1,2,2,3], k = 2:

1. Counts: {1: 3, 2: 2, 3: 1}.
2. Push (3, 1) → heap [(3,1)].
3. Push (2, 2) → heap [(2,2), (3,1)] (size 2, at capacity).
4. Push (1, 3) → size 3 > k, pop the root (1, 3) — the smallest frequency — leaving [(2,2), (3,1)].
5. Extract values: [2, 1] — same set as expected [1, 2] (any order allowed).

Complexity: O(n + d log k) time, O(d) space. Prefer this when k ≪ d or when data arrives as a stream.

Approach 3 — Bucket sort by frequency

Frequencies live in the bounded range 1..n, so instead of comparing them, index by them. This is bucket/counting sort: group items by a small-integer key, then read the groups in key order. buckets[f] collects all values occurring exactly f times; sweeping f from n down to 1 yields values in non-increasing frequency order with no comparison sort at all.

from typing import List
from collections import Counter


def topKFrequent(nums: List[int], k: int) -> List[int]:
    count = Counter(nums)
    buckets: List[List[int]] = [[] for _ in range(len(nums) + 1)]
    for value, freq in count.items():
        buckets[freq].append(value)

    result: List[int] = []
    for freq in range(len(nums), 0, -1):
        for value in buckets[freq]:
            result.append(value)
            if len(result) == k:
                return result
    return result   # unreachable given valid k

Walkthrough on Example 1, nums = [1,1,1,2,2,3], k = 2:

1. Counts: {1: 3, 2: 2, 3: 1}; n = 6, so buckets indexed 0..6.
2. Fill: buckets[3] = [1], buckets[2] = [2], buckets[1] = [3], others empty.
3. Sweep f = 6, 5, 4: empty. f = 3: take 1 (result [1]). f = 2: take 2 → size k, return [1, 2].

Complexity: O(n) time (count, fill, sweep are each linear), O(n) space for the buckets.

Common pitfalls

• Sizing the bucket array to d (distinct count) instead of n + 1 — a value can occur up to n times, so frequency n must have a bucket.
• Using a max-heap of size k: to keep the k largest, you evict the smallest, which needs a min-heap; a max-heap works only if you push all d items and pop k times (O(d + k log d), also fine but a different scheme).
• Pushing raw values into the heap instead of (freq, value) pairs — the heap must be ordered by frequency.
• Sweeping buckets from low to high frequency, which returns the least frequent elements.

Pattern takeaway

“Top-k by some score” decomposes into hash-map counting followed by a selection structure. A size-k min-heap gives O(n log k) and works for streams; when the score is a bounded small integer (a count can’t exceed n), buckets indexed by score replace comparison sorting entirely and reach O(n). “The key is a bounded int, so index by it” is a recurring arrays-and-hashing technique.