MediumArrayHash TableDivide and ConquerSortingHeap (Priority Queue)Bucket SortCountingQuickselect

Top K Frequent Elements

1 approach, code in every language

You are given an integer array and an integer k. Return the k values that occur most often in the array.

The result may be returned in any order, and the problem guarantees that the set of top-k values is unique. Aim for a solution that is faster than fully sorting the array by frequency.

Example 1

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

Output: [1,2]

1 appears three times and 2 appears twice, so they are the two most frequent values.

Example 2

Input: nums = [1], k = 1

Output: [1]

There is only one distinct value, and it is the most frequent.

Constraints

1 <= nums.length <= 10^5
-10^4 <= nums[i] <= 10^4
k is in the range [1, the number of unique elements in the array]
The answer is guaranteed to be unique

Frequency Count + Heap or Bucket Sort

Tally frequencies in a hash map, then either keep a size-k min-heap by frequency or bucket-sort values by their count and read buckets from high to low.

Loading animation…

Intuition

The order of the array does not matter; only how often each value appears. So first tally every value in a hash map with a single pass. Now the task reduces to selecting the k entries with the largest counts. A size-k min-heap keyed by frequency keeps only the strongest candidates, evicting the weakest whenever it overflows, which gives O(n log k). When counts are bounded by n, bucket sort is even better: place each value in a bucket indexed by its frequency and scan buckets from high to low to reach O(n).

Algorithm walkthrough

1Traverse the array once, incrementing each value's count in a hash map.
2Create buckets where bucket[f] holds every value whose frequency equals f (frequencies range from 1 to n).
3Alternatively, push (frequency, value) into a min-heap and pop whenever its size exceeds k.
4To read the answer with buckets, walk frequencies from n down to 1, collecting values until k are gathered.
5Return the collected values.

Implementation

import heapq
from collections import Counter


class Solution:
    def topKFrequent(self, nums: list[int], k: int) -> list[int]:
        counts = Counter(nums)
        heap: list[tuple[int, int]] = []
        for value, freq in counts.items():
            heapq.heappush(heap, (freq, value))
            if len(heap) > k:
                heapq.heappop(heap)
        return [value for _, value in heap]

Time

O(n) with bucket sort, O(n log k) with a size-k heap

Space

O(n)

No frequency can exceed n, which is what makes bucket sort linear. The heap variant is shown for Python/Java/C++/C#/Go and the bucket-sort variant for JavaScript/TypeScript/C.

Create a free account to see the solution

You get the step-by-step animation, the intuition and clean code in every language. Free, no credit card.

Create a free account Already have an account? Sign in

Back to Priority Queues

After the pattern

Now solve one you haven't seen.

Most Reported Calibration Offsets is our own problem on the technique behind Top K Frequent Elements: a new statement, so there's no answer to remember. Write it in your browser and run it against graded tests.

Practise it with tests All practice problems

1,194 problems · 15,062 graded tests · free