# Top K Frequent Elements

- **Canonical ID**: `top-k-frequent-elements`
- **Canonical URL**: https://dsacheatsheet.com/problems/top-k-frequent-elements
- **Difficulty**: medium
- **Patterns**: Arrays & Hashing, Heaps
- **Version**: 1.0.0 (verified 2026-11-11T21:00:00Z)
- **Original Problem**: https://leetcode.com/problems/top-k-frequent-elements/

## 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

- **Time Complexity**: `O(N)`
- **Space Complexity**: `O(N)`
- **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

### Python
```python
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
```

### TypeScript
```typescript
export function topKFrequent(nums: number[], k: number): number[] {
  const count = new Map<number, number>();
  for (const n of nums) count.set(n, (count.get(n) ?? 0) + 1);
  const buckets: number[][] = Array.from({ length: nums.length + 1 }, () => []);
  for (const [n, c] of count) buckets[c].push(n);
  const res: number[] = [];
  for (let i = buckets.length - 1; i > 0 && res.length < k; i--) {
    for (const n of buckets[i]) {
      res.push(n);
      if (res.length === k) return res;
    }
  }
  return res;
}
```

### C++
```cpp
vector<int> topKFrequent(vector<int>& nums, int k) {
    unordered_map<int, int> cnt;
    for (int x : nums) cnt[x]++;
    vector<vector<int>> b(nums.size() + 1);
    for (auto& [x, f] : cnt) b[f].push_back(x);
    vector<int> res;
    for (int f = nums.size(); f > 0 && (int)res.size() < k; --f)
        for (int x : b[f]) if ((int)res.size() < k) res.push_back(x);
    return res;
}
```

### Java
```java
int[] topKFrequent(int[] nums, int k) {
    Map<Integer, Integer> cnt = new HashMap<>();
    for (int x : nums) cnt.merge(x, 1, Integer::sum);
    List<Integer>[] b = new List[nums.length + 1];
    for (var e : cnt.entrySet()) {
        if (b[e.getValue()] == null) b[e.getValue()] = new ArrayList<>();
        b[e.getValue()].add(e.getKey());
    }
    int[] res = new int[k];
    int idx = 0;
    for (int f = nums.length; f > 0 && idx < k; f--) {
        if (b[f] != null) for (int x : b[f]) if (idx < k) res[idx++] = x;
    }
    return res;
}
```

### Go
```go
func topKFrequent(nums []int, k int) []int {
    cnt := map[int]int{}
    for _, x := range nums { cnt[x]++ }
    b := make([][]int, len(nums)+1)
    for x, f := range cnt { b[f] = append(b[f], x) }
    res := []int{}
    for f := len(b) - 1; f > 0 && len(res) < k; f-- {
        for _, x := range b[f] {
            res = append(res, x)
            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.