# Top K Frequent Elements

> How to solve Top K Frequent Elements: find the k most common values by combining a frequency count with a heap or bucket sort.

- Difficulty: Medium
- Category: Arrays & Hashing
- Topics: Array, Hash Table, Heap
- Published 2026-08-21

## Problem

You are given an integer array and a number `k`. Return the `k` values that occur most often; order does not matter, and a well-defined answer of size `k` is guaranteed to exist.

**Example.** For `[1, 1, 1, 2, 2, 3]` with `k = 2`, the answer is `[1, 2]`, since `1` occurs three times and `2` occurs twice, more than `3`.

## Key idea

The first step is always the same: tally how often each distinct value occurs with a hash map, in one linear pass. From there, sorting the distinct values by frequency and taking the top `k` works, but sorting all of them is more effort than the problem needs when `k` is small.

A better approach keeps a min-heap of size `k` while scanning the distinct values: push each frequency in, and whenever the heap grows past `k`, pop the smallest. What remains after every distinct value is processed is exactly the `k` largest frequencies, at a cost of O(log k) per push or pop instead of O(log n). An even faster approach exploits the fact that frequency can never exceed the array length: build an array of buckets indexed by frequency, drop each value into the bucket matching its count, then walk the buckets from the highest frequency down, collecting values until `k` are gathered, with no sorting required.

## Solution

```typescript
function topKFrequent(nums: number[], k: number): number[] {
  const frequency = new Map<number, number>();
  for (const num of nums) {
    frequency.set(num, (frequency.get(num) ?? 0) + 1);
  }

  const buckets: number[][] = Array.from({ length: nums.length + 1 }, () => []); // index = frequency, which can't exceed the array length
  for (const [value, count] of frequency) {
    buckets[count].push(value);
  }

  const result: number[] = [];
  for (let count = buckets.length - 1; count >= 0 && result.length < k; count--) { // walk buckets from highest frequency down
    for (const value of buckets[count]) {
      result.push(value);
      if (result.length === k) {
        break;
      }
    }
  }

  return result;
}
```

## Complexity

- **Time:** O(n) using bucket sort by frequency, since frequency is bounded by the array length; O(n log k) using a size-`k` heap instead.
- **Space:** O(n). The frequency map and the bucket array both scale with the number of elements.

## Watch out for

- Use a min-heap of size `k`, not a max-heap over every element; discarding the smallest as the heap overflows is what keeps the work bounded by `k` rather than by the number of distinct values.
- Bucket sort by frequency only works because the count is bounded by the array length, even though the values themselves can be arbitrary integers.

## Pattern

This is "count, then select": tally frequencies first, then use a bounded-size heap or a bucket sort keyed by count to pick the top or bottom few without fully sorting everything.

---

Canonical URL: https://www.marauderbot.com/questions/top-k-frequent-elements
