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’s single occurrence loses.

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.

n up to 10^5 makes counting cheap; the interesting part 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)

The naive intuition: tally frequencies with a hash map, sort every distinct value by its count, take the top k.

from typing import List
from collections import Counter


class Solution:
    def topKFrequent(self, 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

The insight: 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, 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


class Solution:
    def topKFrequent(self, 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. This is the go-to when k ≪ d or when data arrives as a stream.

Approach 3 — Bucket sort by frequency

The insight: frequencies live in the bounded range 1..n, so instead of comparing them, index by them — the essence of bucket/counting sort (group items by a small-integer key, then read 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


class Solution:
    def topKFrequent(self, 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, then 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). Recognizing “the key is a bounded int → index by it” is the recurring arrays-and-hashing move.