Top K Frequent Elements: 5 Smart Tricks That Save the Day

Top K Frequent looks like a sorting problem. It's a counting problem in disguise.

The reflex is count-then-sort-all. That runs O(u log u) on distinct elements — fine, but it's not linear. You'll pass and still miss the point. The follow-up 'now do it in O(n)' ends rounds.

The answer is bucket sort on frequencies. Counts range from 1 to n, so index buckets by frequency and walk down. That's O(n) time, O(n) space, and the pattern behind a dozen frequency problems. Learn the buckets, not just the heap.

Return the K Most Frequent Values, in Any Order

Given integer array nums and integer k, return the k most frequent elements in any order. Example: [1,1,1,2,2,3], k=2 → [1,2] (frequencies 3,2,1). Guaranteed: k is valid (1 <= k <= distinct count). Ties beyond k accept any choice.

Constraints: n to 10^5, values ±10^4, k ≤ distinct count. O(n log n) full sorts pass but invite the linear follow-up. Output order is free — graders compare sets.

Walk the example: counts {1:3, 2:2, 3:1}. Buckets size 7 (n+1=7): bucket[3]=[1], bucket[2]=[2], bucket[1]=[3]. Walk down from 6: empty... 3 → take 1; 2 → take 2. Collected 2 = k. Done: [1,2]. Each number placed once, read once.

Sorting by Frequency Is O(n log n) — Slower Than Required

Count-then-full-sort: Counter in O(n), then sort u distinct keys by frequency in O(u log u). Total O(n + u log u), space O(n). At u = 10^5 that's ~1.7M comparisons — passes in PyPy usually, but it is not linear and dies on strict follow-ups.

Min-heap-of-k improves selection to O(n log k): push (freq, num), cap size at k. Good when k is tiny; converges to full-sort cost as k → u. Neither is the linear answer.

Interview play: 'Sort-all is O(u log u) — passes but not linear. Frequencies are bounded by n, so buckets give true O(n).' Claim nothing you can't prove; the bound is the interview.

Bucket Sort: Index by Frequency Instead of by Value

Frequencies lie in 1..n, a bounded integer range — bucket sort applies. Steps: counts = Counter(nums) O(n); buckets = [n+1 empty lists]; for num, c in counts.items(): buckets[c].append(num) — each distinct placed once; walk freq from n down to 1, extending result, stopping at exactly k.

Why linear: counting touches n elements; placement touches u distinct; collection scans n+1 buckets plus k picks. Total O(n). Space O(n): counts plus buckets hold u references. Correctness: bucket[c] holds exactly the numbers with frequency c, so descending collection yields non-increasing frequencies and the first k are top-k (ties arbitrary but valid).

Beats heaps asymptotically when k grows: heap costs O(n log k) → O(n log n) at k ~ u, buckets stay O(n). Heaps win only on streaming memory (O(k) selection state) — name that trade-off live.

The Bucket-Sort Solution in Full Python

The code above is the complete LeetCode submission. Trace [1,1,1,2,2,3], k=2: counts {1:3,2:2,3:1}; buckets[3]=[1], buckets[2]=[2], buckets[1]=[3]; walk 6..4 empty, 3 → [1], 2 → [1,2], len == k → return [1,2].

Trace [7,7,7], k=1: buckets size 4, buckets[3]=[7]; walk 3 → [7], return. No crash — slot n exists. Complexity O(n) time, O(n) space.

from collections import Counter

class Solution:
    def topKFrequent(self, nums: list[int], k: int) -> list[int]:
        counts = Counter(nums)
        buckets: list[list[int]] = [[] for _ in range(len(nums) + 1)]
        for num, c in counts.items():
            buckets[c].append(num)
        res: list[int] = []
        for freq in range(len(nums), 0, -1):
            for num in buckets[freq]:
                res.append(num)
                if len(res) == k:
                    return res
        return res

Ties at the K Boundary, k = n and Single-Element Arrays

All-same [7,7,7] k=1 → [7] (needs slot n). Single [1] k=1 → [1]. Full-tie [1,1,2,2,3,3] k=2 → any 2 of the 3 (grader accepts sets). k = distinct count returns everything. Negative and large values behave identically — hashing is value-agnostic.

Empty-bucket walk cost: scanning n+1 buckets is O(n) regardless — no action needed. Early-stop placement (return inside loops) avoids flag variables; confirm both loops exit via the return, not just the inner one.

Why Buckets Beat a Heap Once k Approaches n

Time O(n): count (n) + place (u) + scan buckets (n+1) + collect (k) — all linear terms. Space O(n): counts (u) + buckets (u references + n+1 lists). Optimal in the comparison-free sense: each element must be counted (Ω(n) floor), and counts must be stored (Ω(u) floor).

Whiteboard closer: 'Bounded frequencies index buckets — linear, no comparisons.' Then bridge: 'Streaming data swaps buckets for a k-capped heap O(n log k); clusters shard by hash and merge counts.' One problem, three deployment stories.