Top K Frequent Elements

1. Define the problem

Given an integer array nums and an integer k, return the k most frequent elements. You may return the answer in any order . Count each value, then keep a min-heap of size k keyed by frequency. A new value only earns a spot if it beats the least-frequent value currently kept.

Constraints

1 ≤ nums.length ≤ 10⁵
-10⁴ ≤ nums_i ≤ 10⁴
k is in the range [1, the number of distinct elements in nums]

Example

Inputnums = [1, 1, 1, 2, 2, 3], k = 2

Output[1, 2]

Explanation 1 appears 3 times, 2 appears 2 times, 3 appears once — the top 2 are 1 and 2.

2. Know the words first

In plain terms

Min-heap of size k: A heap capped at k elements holding the k highest-frequency values seen so far, with the least frequent of those k at the root.

3. Visualize the solution

Count frequencies, keep the k most frequent in a heap

slot 0—

slot 1—

Statuscount

Frequencies: 1 → 3, 2 → 2, 3 → 1. The heap is still empty — both slots show —.

What happens in this step

scan nums = [1, 1, 1, 2, 2, 3]

counts: 1 → 3, 2 → 2, 3 → 1

Each value's tally comes from a single pass with a hash map. These (count, value) pairs are what gets pushed into the heap next, in this same order: 1, then 2, then 3.

The row below is the heap's array. With k = 2 it never holds more than two entries, and right now it holds none.

Step 1 of 4

Steps to visualize

Count how many times each value appears using a hash map.
The row is the heap array: k = 2 slots. A slot marked — is still empty.
Push (frequency, value) pairs into a min-heap capped at size k.
If a new pair has a higher frequency than the heap root, swap it in.
After processing every value, the heap holds exactly the k most frequent values.

4. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

Count frequencies, keep the k most frequent in a heap

slot 0—

slot 1—

Statuscount

Frequencies: 1 → 3, 2 → 2, 3 → 1. The heap is still empty — both slots show —.

What happens in this step

scan nums = [1, 1, 1, 2, 2, 3]

counts: 1 → 3, 2 → 2, 3 → 1

Each value's tally comes from a single pass with a hash map. These (count, value) pairs are what gets pushed into the heap next, in this same order: 1, then 2, then 3.

The row below is the heap's array. With k = 2 it never holds more than two entries, and right now it holds none.

Step 1 of 4

5. Solution

Solution

solution.tsTypeScript

function topKFrequent(nums, k) {
  const counts = new Map();
  for (const num of nums) counts.set(num, (counts.get(num) || 0) + 1);

  const heap = []; // entries stored as [count, value]

  function push(item) {
    heap.push(item);
    let i = heap.length - 1;
    while (i > 0) {
      const parent = (i - 1) >> 1;
      if (heap[parent][0] > heap[i][0]) {
        [heap[parent], heap[i]] = [heap[i], heap[parent]];
        i = parent;
      } else {
        break;
      }
    }
  }

  function siftDown() {
    let i = 0;
    const size = heap.length;
    while (true) {
      let smallest = i;
      const left = 2 * i + 1;
      const right = 2 * i + 2;
      if (left < size && heap[left][0] < heap[smallest][0]) smallest = left;
      if (right < size && heap[right][0] < heap[smallest][0]) smallest = right;
      if (smallest === i) break;
      [heap[i], heap[smallest]] = [heap[smallest], heap[i]];
      i = smallest;
    }
  }

  function pop() {
    const top = heap[0];
    const last = heap.pop();
    if (heap.length > 0) {
      heap[0] = last;
      siftDown();
    }
    return top;
  }

  for (const [value, count] of counts) {
    if (heap.length < k) {
      push([count, value]);
    } else if (count > heap[0][0]) {
      pop();
      push([count, value]);
    }
  }

  return heap.map((entry) => entry[1]);
}

Time: O(n log k)
Space: O(n)

6. Test cases

Test cases

Input	Expected	Covers
`nums = [1, 1, 1, 2, 2, 3], k = 2`	`[1, 2]`	example from the docstring
`nums = [1], k = 1`	`[1]`	smallest valid input, a single distinct value
`nums = [4, 5, 6, 7], k = 2`	`[4, 5]`	every value has the same frequency, ties broken by scan order
`nums = [-1, -1, -2, -3, -3, -3], k = 1`	`[-3]`	negative numbers with a clear frequency winner
`nums = [5, 5, 5, 5, 2, 2, 8], k = 2`	`[5, 2]`	a large gap between the most and least frequent values
`nums = [1, 2, 2, 3, 3, 3], k = 3`	`[1, 2, 3]`	k equals the number of distinct values, everything is returned

Top K Frequent Elements