LeetCode 347 · Hash Map · Bucket Sort

Top K Frequent Elements

MediumReturn the k values that appear most often — in O(n) with bucket sort.
Given an integer array nums and an integer k, return the k most frequent elements. You may return the answer in any order.

Walkthrough

try:
1
function topKFrequent(nums, k) {
2
  const count = new Map();
◄
3
  for (const n of nums) count.set(n, (count.get(n) || 0) + 1);
4
  const buckets = Array.from({length: nums.length+1}, () => []);
5
  for (const [n, c] of count) buckets[c].push(n);
6
  const res = [];
7
  for (let c = buckets.length-1; c > 0 && res.length < k; c--)
8
    for (const n of buckets[c]) {
9
      res.push(n);
10
      if (res.length === k) return res;
11
    }
12
  return res;
13
}
k = 2
nums
1
1
1
2
2
3
count (value → frequency)
(empty)
buckets (by frequency, high → low)
×3—
×2—
×1—
result
[]
STEP 0 / 15 · line 2
Start
Goal: the 2 most frequent values. Step 1 — count how often each value appears.

Intuition

First tally how many times each value occurs using a hash map.

The highest frequency any value can have is the array length, so make one bucket per possible frequency.

Drop each value into the bucket matching its count — this groups by frequency without sorting (no n·log n).

Walk the buckets from the highest frequency downward, collecting values until you have k.

The algorithm

  1. 01Count occurrences of each value in a map.
  2. 02Create buckets indexed by frequency (0..n).
  3. 03Place each value in the bucket equal to its count.
  4. 04Scan buckets high → low, collecting values until k are gathered.

Reference implementation

1
function topKFrequent(nums, k) {
2
  const count = new Map();
3
  for (const n of nums) count.set(n, (count.get(n) || 0) + 1);
4
  const buckets = Array.from({ length: nums.length + 1 }, () => []);
5
  for (const [n, c] of count) buckets[c].push(n);
6
  const res = [];
7
  for (let c = buckets.length - 1; c > 0 && res.length < k; c--) {
8
    for (const n of buckets[c]) {
9
      res.push(n);
10
      if (res.length === k) return res;
11
    }
12
  }
13
  return res;
14
}

Complexity

Time
O(n) — counting, bucketing, and scanning are each linear.
Space
O(n) for the count map and the buckets.