Skip to content
16-Week DSA Roadmap
LeetCode #347MediumProblem 5 of 8

Top K Frequent Elements

Find the k numbers that appear most often in an array.

  • Frequency counting
  • Bucket sort

Before this, know: Frequency counting with a hash map (see Valid Anagram), Arrays of arrays

The problem in plain English

You get an array of numbers nums and a number k. Return the k numbers that appear most often. The frequency of a number is how many times it appears.

Example: nums = [1, 1, 1, 2, 2, 3] and k = 2.

nums
  1. 10
  2. 11
  3. 12
  4. 23
  5. 24
  6. 35
count3 items
numbertimes
13
22
31
1 appears 3 times, 2 appears twice, 3 appears once. The top 2 are 1 and 2.

So the answer is [1, 2]. The rules that matter:

  • Return the numbers themselves (not their counts), in any order.
  • LeetCode promises the answer is unique: there’s never a tie at the cut-off that makes two different answers possible.
  • k is between 1 and the number of different values.
  • The follow-up asks for something better than O(n log n), which rules out plain sorting. Keep that in mind. (Big-O notation is a short way of saying how the work grows as the input grows; O(n log n) is what sorting n items costs. See Big-O in 5 minutes.)

Before you code: think it through

The work splits into two parts:

  1. Count how often each number appears (frequency counting, exactly as in Valid Anagram).
  2. Pick the k biggest counts.

Part 1 is easy and fast with a hash map: a lookup table from a key (here, a number) to a value (here, its count), Map in JavaScript and dict in Python, that finds a key in about one step (see What is a hash map?). The interesting question is part 2.

Pause and think

nums has 6 numbers. What is the largest frequency any number could possibly have? What does that tell you about how many 'shelves' you need?

Approach 1: Count, then sort by count

The natural first idea: count with a hash map, list the different numbers, sort them by count from biggest to smallest, and take the first k.

Count, then sort by count

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

nums
  1. 10
  2. 11
  3. 12
  4. 23
  5. 24
  6. 35
count1 item
numbertimes
11
  • Looking at now
  • Just counted
  • Answer

Count nums[0] = 1: count[1] is now 1.

Step 1 / 9

Which line is running?

function topKFrequent(nums, k) {  const count = new Map(); // number -> how many times it appears  for (const num of nums) {Running now:     count.set(num, (count.get(num) ?? 0) + 1);  }  const distinct = [...count.keys()];  distinct.sort((a, b) => count.get(b) - count.get(a)); // most frequent first  return distinct.slice(0, k);}

Count, then sort

function topKFrequent(nums, k) {  const count = new Map(); // number -> how many times it appears  for (const num of nums) {    count.set(num, (count.get(num) ?? 0) + 1);  }  const distinct = [...count.keys()];  distinct.sort((a, b) => count.get(b) - count.get(a)); // most frequent first  return distinct.slice(0, k);}
def top_k_frequent(nums, k):    count = {}  # number -> how many times it appears    for num in nums:        count[num] = count.get(num, 0) + 1    distinct = list(count.keys())    distinct.sort(key=lambda x: count[x], reverse=True)  # most frequent first    return distinct[:k]

Why isn’t this good enough?

Counting is n steps. Sorting m different numbers costs about m × log m steps. In the worst case every number is different (m = n), so the whole thing is O(n log n). For 100,000 numbers that’s roughly 1.7 million steps. That’s honestly fine in practice, but the follow-up explicitly asks to beat O(n log n), so we need to avoid a full sort.

The heap idea (in words)

A heap (a “priority queue”) is a structure that always hands you its smallest (or largest) item in about log k steps. Keep a heap of the k most frequent numbers seen so far, with the least frequent of them on top. For each number, push it in; if the heap grows past k, pop the least frequent one off. At the end, the heap holds the top k. That’s O(n log k), which beats O(n log n) when k is small. JavaScript has no built-in heap; Python has heapq. Heaps come later in the roadmap. Next we’ll see a trick that’s even faster and needs nothing new.

The pattern: bucket sort by frequency

Sorting compares numbers with each other. But frequencies are small whole numbers between 1 and n, so we can use a frequency as an index and drop each number straight into its slot. Using values as positions to avoid comparing is called bucket sort.

Pattern

Bucket sort / top K by frequency

Template

Use it when: you need the most (or least) frequent items, and the counts are bounded by the input size.

Signal words

  • “top k”
  • “k most frequent”
  • “sort by frequency”
  • “most common”
  • “better than O(n log n)”
buckets
  1. 0
  2. 3
    1
  3. 2
    2
  4. 1
    3
  5. 4
  6. 5
  7. 6

↑ bucket number = how many times

buckets[f] holds the numbers that appear exactly f times. For [1, 1, 1, 2, 2, 3]: 3 is in bucket 1, 2 is in bucket 2, 1 is in bucket 3. Reading from the right gives 1, then 2.

Approach 2: Count, then bucket by frequency

  1. Count: build a hash map count of number → frequency.
  2. Make buckets: an array of n + 1 empty lists. buckets[f] will hold every number that appears exactly f times.
  3. Fill: for each (number, frequency) in count, append the number to buckets[frequency].
  4. Collect: walk f from n down to 1. Take every number in buckets[f] and add it to result. As soon as result has k numbers, return it.

Press Play. Watch the three stages: the count map filling, numbers dropping into the bucket that matches their count, then the scan from the right. Try the “tie in a bucket” example, where two numbers share a bucket.

Count, then bucket by frequency

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

nums
  1. 10
  2. 11
  3. 12
  4. 23
  5. 24
  6. 35
count1 item
numbertimes
11
result
  1. empty
variables
k
2
f
—
  • Looking at now
  • Just changed
  • Bucket we're reading
  • In the answer

Step 1, counting. nums[0] = 1: first time we see it, so count[1] = 1.

Step 1 / 17

Which line is running?

function topKFrequent(nums, k) {  const count = new Map(); // number -> how many times it appears  for (const num of nums) {Running now:     count.set(num, (count.get(num) ?? 0) + 1);  }  // buckets[f] holds every number that appears exactly f times  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; f--) {    for (const num of buckets[f]) {      result.push(num);      if (result.length === k) return result;    }  }  return result; // never reached: k is at most the number of distinct values}

Notice that most buckets stay empty. That’s fine: walking past an empty bucket costs one step, and there are only n + 1 of them.

The code, line by line

Count, then bucket

function topKFrequent(nums, k) {  const count = new Map(); // number -> how many times it appears  for (const num of nums) {    count.set(num, (count.get(num) ?? 0) + 1);  }  // buckets[f] holds every number that appears exactly f times  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; f--) {    for (const num of buckets[f]) {      result.push(num);      if (result.length === k) return result;    }  }  return result; // never reached: k is at most the number of distinct values}
def top_k_frequent(nums, k):    count = {}  # number -> how many times it appears    for num in nums:        count[num] = count.get(num, 0) + 1    # buckets[f] holds every number that appears exactly f times    buckets = [[] for _ in range(len(nums) + 1)]    for num, freq in count.items():        buckets[freq].append(num)    result = []    for f in range(len(buckets) - 1, 0, -1):        for num in buckets[f]:            result.append(num)            if len(result) == k:                return result  # we have our k numbers    return result  # never reached: k is at most the number of distinct values

JavaScript’s closing braces push its line numbers ahead of Python’s from line 5 on; we give both where they differ.

  • Line 1: define the function. (LeetCode uses var topKFrequent = function(nums, k) in JS and def topKFrequent(self, nums, k) inside class Solution in Python.)
  • Lines 2–4: the frequency count. count.get(num) ?? 0 / count.get(num, 0) means “the count so far, or 0 if this is the first time”.
  • Line 7 (JS) / line 6 (Python): n + 1 empty lists, indexes 0 to n. We need index n because a number could appear n times. Index 0 is never used (every number in count appears at least once); it’s there so that buckets[f] lines up with f. Note Array.from({ length }, () => []) creates a separate empty list for each slot.
  • Lines 8–9 (JS) / lines 7–8 (Python): drop each number into the bucket for its frequency. No comparisons, no sorting.
  • Line 12 (JS) / line 10 (Python): walk the buckets from the highest frequency down to 1. In Python range(len(buckets) - 1, 0, -1) counts down and stops before 0.
  • Lines 13–15 (JS) / lines 11–14 (Python): take each number from the bucket, and return as soon as we have k.
  • The last line is a safety net. Since k is never more than the number of different values, we always return earlier.

Dry run

stagewhat happensstate afterwards
countwalk numscount = {1: 3, 2: 2, 3: 1}
make7 empty buckets (0 to 6)[[], [], [], [], [], [], []]
fill1 → bucket 3, 2 → bucket 2, 3 → bucket 1[[], [3], [2], [1], [], [], []]
collect f = 6, 5, 4empty, skipresult = []
collect f = 3take 1result = [1]
collect f = 2take 2: that's k = 2return [1, 2]
nums = [1, 1, 1, 2, 2, 3], k = 2

Look at the “fill” row: in one walk over the count map, every number lands in the right place. A sort would have needed to compare them.

Complexity

Here n is the length of nums.

Count, then sort

Time

O(n log n)

Counting is n steps; sorting up to n different numbers is about n × log n.

Space

O(n)

The count map and the list of distinct numbers.

Count, then heap of size k

Time

O(n log k)

Each of up to n numbers is pushed into a heap that never holds more than k, costing about log k each.

Space

O(n)

The count map (n) plus the heap (k).

Count, then bucket sort

Time

O(n)

Counting is n steps, filling buckets is at most n, and the final walk visits n + 1 buckets and at most n numbers. Three straight passes.

Space

O(n)

The count map plus n + 1 buckets holding each distinct number once.

Common mistakes and edge cases

What to say out loud, in this order:

  1. “Two parts: count frequencies with a hash map, then select the top k.”
  2. “Sorting by count is O(n log n). A min-heap of size k is O(n log k).”
  3. “Frequencies are between 1 and n, so I can bucket by frequency: O(n) overall.”
  4. Point out the n + 1 bucket size and the early stop at k.

Likely follow-up questions:

  • “What if k is close to n?” The bucket approach is O(n) either way; a heap of size k would be close to O(n log n).
  • “What if the data is a stream and doesn’t fit in memory?” Be careful: the count map still holds one entry per different value, so the heap doesn’t shrink that. A heap of size k only bounds the selection step (it holds k items instead of n + 1 buckets). If even one count per different value doesn’t fit, you need an approximate method that trades a little accuracy for much less memory.
  • “Top k frequent words, ties broken alphabetically?” Sort the words inside each bucket, or use a heap with a custom comparison.

Related problems:

  • Valid Anagram (this week): the counting step on its own.
  • Group Anagrams (this week): grouping things under a shared key, like grouping numbers under their frequency here.
  • Contains Duplicate (this week): the simplest “has it appeared before?” question.