Top K Frequent Elements

Medium#347k largest

You get an array of integers and a number k. Return the k numbers that appear most often, in any order; the answer is always unique. Our example: [9, 1, 9, 4, 1, 4, 1, 4] and k = 2 — the answer is [4, 1]: 4 and 1 appear 3 times each, 9 only twice.

347 Top K Frequent ElementsWalkthrough · 1×

Example: [9, 1, 9, 4, 1, 4, 1, 4], k = 2. Top row: the numbers; then their counts; below, the min-heap ordered by count, the count under each number.

91941414count—min-heapby count
not counted yetcurrent xcounted; in the heaproot: the rarest in the heapdroppedanswer

Nothing counted yet: count = {}

01/29
restart · back · play · step
Speed
1function topKFrequent(nums, k):
2 count = empty map // missing keys: 0
3 for each x in nums:
4 count[x] = count[x] + 1
5 heap = empty min-heap // ordered by count[x]
6 for each x in keys of count:
7 push x into heap
8 if size of heap > k:
9 pop min from heap // the rarest
10 return heap
state
count
{}
x
–
heap
–
historyclick a step to go back

← → step · space play/pause

Why it works

  1. The heap is the card’s k largest with another key: it compares how often numbers appear, not the numbers themselves. So 9, the largest number, is popped, because it is the rarest.
  2. Each distinct number goes through the heap once, and whenever there are k + 1 the rarest of them leaves. So the k most frequent stay to the end.
  3. The heap holds at most k + 1 numbers, so with many distinct numbers it is cheaper than sorting all of them by count.

Complexity

Time O(n + m log k): one pass to count n numbers, then m distinct numbers through a heap of at most k + 1. Memory O(m) for the counts.

nextNow solve it yourself, no hints.

Solve on LeetCode ↗

The problem and its statement belong to LeetCode. Here are our own retelling, example and solution. Patterns Hero is not affiliated with LeetCode.