DSAPrep
MediumArrays & Hashing

Top K Frequent Elements

Given an integer array nums and an integer k, return the k most frequent elements. You may return the answer in any order.

Example 1

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

Example 2

Input: nums = [1], k = 1
Output: [1]

Example 3

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

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].
  • It is guaranteed that the answer is unique.
Follow-up: Your algorithm's time complexity must be better than O(n log n), where n is the array's size.
View original on LeetCode ↗

The first step is always the same: count how often each number appears. What differs is how we pull out the top k from those counts — sorting them is the obvious way, but the follow-up asks for something that doesn’t pay a log n penalty, which points at bucket sort.

Count, Then Sort

Time O(n log n)Space O(n)

Count frequencies with a hash map, then sort the items by frequency and take the top k.

from collections import Counter


class Solution:
    def topKFrequent(self, nums: list[int], k: int) -> list[int]:
        counts = Counter(nums)
        ordered = sorted(counts.items(), key=lambda pair: -pair[1])
        return [num for num, _ in ordered[:k]]

Counting is O(n), but sorting the (at most n) distinct counts is O(n log n) — and we only actually needed the top k, not a full ordering of every frequency.

Bucket Sort by Frequency

OptimalTime O(n)Space O(n)

A count can never exceed n (the array length), so instead of sorting, create n + 1 buckets indexed by frequency and drop each number into the bucket matching its count. Reading the buckets from highest frequency down and collecting numbers until we have k gives the answer without ever comparing counts against each other.

from collections import Counter


class Solution:
    def topKFrequent(self, nums: list[int], k: int) -> list[int]:
        counts = Counter(nums)
        buckets = [[] for _ in range(len(nums) + 1)]
        for num, freq in counts.items():
            buckets[freq].append(num)


        result = []
        for freq in range(len(buckets) - 1, 0, -1):
            for num in buckets[freq]:
                result.append(num)
                if len(result) == k:
                    return result
        return result

Tracing the counting pass over nums = [1, 1, 1, 2, 2, 3]:

1
0
1
1
1
2
2
3
2
4
3
5
num = 1

Hash Map

1 → 1
1 / 6
resultcurrent

Count 1. Frequency of 1 is now 1.

After counting, bucket 3 holds [1], bucket 2 holds [2], and bucket 1 holds [3]. Reading from bucket index 6 down to 1 and stopping once k = 2 numbers are collected yields 1 (from bucket 3) then 2 (from bucket 2) — [1, 2].

Correctness: every distinct number lands in exactly one bucket, indexed by its true frequency. Scanning buckets from the highest index down visits numbers in strictly non-increasing frequency order, so the first k numbers collected are exactly the k most frequent.

Complexity: counting is O(n); placing each of the at most n distinct numbers into a bucket is O(n); reading buckets visits at most n + 1 buckets and n numbers total — O(n) time overall, meeting the follow-up. Counts and buckets together hold O(n) entries — O(n) space.