Typorithm · medium

Top K Frequent

top-k-frequentarrays-hashingbucket-sortfrequency-countlinear

Saved on this device

Full lesson · 8 learning steps Open any exercise for focused practice

Step 1 of 8 · intro card

Learn Top K Frequent

Arrays & Hashing

Count frequencies, bucket values by count, then read buckets from high to low for the top k.

A heap solves this in O(n log k), but bucket sort by frequency is O(n).

Since no frequency exceeds n, an array of n+1 buckets indexes them exactly.

Reading buckets from the highest count down yields the most frequent values first.

Bucket index = frequency.

Max frequency is n.

Scan high to low for top k.

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

  const buckets = Array.from({ length: nums.length + 1 }, () => []);
  for (const [num, freq] of count) {
    buckets[freq].push(num);
  }

  const result = [];
  for (let f = buckets.length - 1; f >= 0 && result.length < k; f -= 1) {
    for (const num of buckets[f]) {
      result.push(num);
    }
  }

  return result.slice(0, k);
}

Read the implementation

Connect each part of the code to the concept before you type.

1. Count frequencies

Tally how often each value appears.

count.set(num, (count.get(num) ?? 0) + 1)

2. Frequency buckets

Index buckets by frequency; max frequency is n.

const buckets = Array.from({ length: nums.length + 1 }, () => [])

3. Bucket by count

Place each value in the bucket for its frequency.

buckets[freq].push(num)

4. High to low

Walk buckets from highest frequency until k are collected.

for (let f = buckets.length - 1; f >= 0 && result.length < k; f -= 1)

A complete learning loop

Understand

Read the concept map and follow the code breakdown.

Reconstruct

Type the implementation, repair mistakes and work through every recall exercise.

Verify

Use the final check without hints; revisit weak concepts in short practice sessions.