DSA Tracker

Visualize

Top K Frequent Elements

Min-heap of size k

time O(n log k)space O(k)

The insight: finding the top k by frequency doesn't require sorting every distinct value — you only need to track the k most frequent seen so far and be willing to evict the weakest one when a stronger candidate shows up. A min-heap capped at size k does this cheaply: its root is always the least frequent of the current k candidates, so any new element only has to beat that root to earn a spot, and popping the root when the heap overflows keeps exactly the k highest counts. That's O(n log k) instead of sorting all distinct counts.

Details

Animated on: Find the k most frequent elements from an array

Problem:Top K Frequent ElementsMedium

Pattern:Hashing and Frequency MapsHeap and Top K

Min-heap of size k

step 1 / 7

1
[0]
1
[1]
1
[2]
2
[3]
2
[4]
3
[5]

Process num=1 (appears 3 times in nums). Count map starts. Min-heap: [1 cnt=3]. Size 1 ≤ k=2. Keep.

  • root=0· arr[0] = 1
Pseudocode
1FUNCTION topKFrequent(nums, k):
2  cnt = a lookup table (number → its count)
3  FOR each n in nums: add one to cnt[n]
4  h = a min-heap keyed by count (least frequent on top)
5  FOR each (number n, count c) in cnt:
6    push (count c, number n) onto the heap
7    IF heap size > k: pop the least frequent (the min)
8  END FOR
9  RETURN the number from each entry left in the heap
10END FUNCTION

← / → step · space play · Home restart

Every step in words

Show all 7 steps
  1. Process num=1 (appears 3 times in nums). Count map starts. Min-heap: [1 cnt=3]. Size 1 ≤ k=2. Keep.
  2. Add num=1 to min-heap. Heap: [1 cnt=3]. Size 1 ≤ k=2. Keep current element as most frequent.
  3. Add num=2 (appears 2 times) to min-heap. Heap: [1 cnt=3, 2 cnt=2]. Size 2 ≤ k=2. Both kept as top candidates.
  4. Add num=3 (appears 1 time) to min-heap. Heap: [1 cnt=3, 2 cnt=2, 3 cnt=1]. Size 3 > k=2. Remove minimum count element: num=3 (cnt=1) discarded. Heap: [1 cnt=3, 2 cnt=2]. Size 2 = k.
  5. Heap final state: k=2 most frequent elements. Elements: 1 (cnt=3) and 2 (cnt=2). Top 2 most frequent by count.
  6. Extract result: top K = [1, 2]. These are the 2 most frequent elements with counts 3 and 2 respectively.
  7. Return [1, 2] — the k=2 most frequent elements (counts 3 and 2), correctly kept by the size-k min-heap.

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Top K Frequent Elements in the editorAll Heap problemsBack to roadmap