Top K Frequent Elements

mediumTests passed 2026-11-11v1.0.0
TC: O(N)|SC: O(N)
Arrays & HashingHeapsOriginal Statement (leetcode).md

1. Core Invariant / The Trick

Bucket Sort on Frequency: count occurrences in a hash map, then place elements at index `buckets[freq]` (size `N + 1`). Scan buckets from N down to 1 to harvest top k in strictly linear O(N) time.

2. Complexity Bounds & Proof

Maximum frequency is bounded by array length N, enabling O(N) bucket indexing instead of O(N log k) heap sorting.

3. Minimal Idiomatic Code

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

4. Failure Modes & Interview Follow-ups

Pitfalls:- Bucket index ranges `0..N`, so allocate `N + 1` buckets.
Follow-ups:- Streaming data: switch to min-heap of size k.

Personal Notes & Scratchpad (Local-First Yjs CRDT)

Saved instantaneously in IndexedDB. Streams live across peers via Hocuspocus when signed in.

Related Invariants

Kth Largest Element in a Stream (O(N log k))
Browser Scratchpad
Console Output
Click Run or press Cmd/Ctrl+Enter to execute locally in a Web Worker.