347. Top K Frequent Elements - Explanation

Problem Link

Description

Given an integer array nums and an integer k, return the k most frequent elements within the array.

The test cases are generated such that the answer is always unique.

You may return the output in any order.

Example 1:

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

Output: [2,3]

Example 2:

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

Output: [7]

Constraints:

  • 1 <= nums.length <= 10^4.
  • -1000 <= nums[i] <= 1000
  • 1 <= k <= number of distinct elements in nums.


Recommended Time & Space Complexity

You should aim for a solution with O(n) time and O(n) space, where n is the size of the input array.


Hint 1

A naive solution would be to count the frequency of each number and then sort the array based on each element’s frequency. After that, we would select the top k frequent elements. This would be an O(nlogn) solution. Though this solution is acceptable, can you think of a better way?


Hint 2

Can you think of an algorithm which involves grouping numbers based on their frequency?


Hint 3

Use the bucket sort algorithm to create n buckets, grouping numbers based on their frequencies from 1 to n. Then, pick the top k numbers from the buckets, starting from n down to 1.


Company Tags

Please upgrade to NeetCode Pro to view company tags.



1. Sorting

Intuition

To find the k most frequent elements, we first need to know how often each number appears.
Once we count the frequencies, we can sort the unique numbers based on how many times they occur.
After sorting, the numbers with the highest frequencies will naturally appear at the end of the list.
By taking the last k entries, we get the k most frequent elements.

This approach is easy to reason about:
count the frequencies → sort by frequency → take the top k.

Algorithm

  1. Create a hash map to store the frequency of each number.
  2. Build a list of [frequency, number] pairs from the map.
  3. Sort this list in ascending order based on frequency.
  4. Create an empty result list.
  5. Repeatedly pop from the end of the sorted list (highest frequency) and append the number to the result.
  6. Stop when the result contains k elements.
  7. Return the result list.
class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        count = {}
        for num in nums:
            count[num] = 1 + count.get(num, 0)

        arr = []
        for num, cnt in count.items():
            arr.append([cnt, num])
        arr.sort()

        res = []
        while len(res) < k:
            res.append(arr.pop()[1])
        return res

Time & Space Complexity

  • Time complexity: O(nlog⁡n)O(n \log n)
  • Space complexity: O(n)O(n)

2. Min-Heap

Intuition

After counting how often each number appears, we want to efficiently keep track of only the k most frequent elements.
A min-heap is perfect for this because it always keeps the smallest element at the top.
By pushing (frequency, value) pairs into the heap and removing the smallest whenever the heap grows beyond size k, we ensure that the heap always contains the top k most frequent elements.
In the end, the heap holds exactly the k values with the highest frequencies.

Algorithm

  1. Build a frequency map that counts how many times each number appears.
  2. Create an empty min-heap.
  3. For each number in the frequency map:
    • Push (frequency, number) into the heap.
    • If the heap size becomes greater than k, pop once to remove the smallest frequency.
  4. After processing all numbers, the heap contains the k most frequent elements.
  5. Pop all elements from the heap and collect their numbers into the result list.
  6. Return the result.
class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        count = {}
        for num in nums:
            count[num] = 1 + count.get(num, 0)

        heap = []
        for num in count.keys():
            heapq.heappush(heap, (count[num], num))
            if len(heap) > k:
                heapq.heappop(heap)

        res = []
        for i in range(k):
            res.append(heapq.heappop(heap)[1])
        return res

Time & Space Complexity

  • Time complexity: O(nlog⁡k)O(n \log k)
  • Space complexity: O(n+k)O(n + k)

Where nn is the length of the array and kk is the number of top frequent elements.

3. Bucket Sort

Intuition

Each number in the array appears a certain number of times, and the maximum possible frequency is the length of the array.
We can use this idea by creating a list where the index represents a frequency, and at each index we store all numbers that appear exactly that many times.

For example:

  • All numbers that appear 1 time go into group freq[1].
  • All numbers that appear 2 times go into group freq[2].
  • And so on.

After we build these groups, we look from the highest possible frequency down to the lowest and collect numbers from these groups until we have k of them.
This way, we directly jump to the most frequent numbers without sorting all the elements by frequency.

Algorithm

  1. Build a frequency map that counts how many times each number appears.
  2. Create a list of groups freq, where freq[i] will store all numbers that appear exactly i times.
  3. For each number and its frequency in the map, add the number to freq[frequency].
  4. Initialize an empty result list.
  5. Loop from the largest possible frequency down to 1:
    • For each number in freq[i], add it to the result list.
    • Once the result contains k numbers, return it.
class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        count = {}
        freq = [[] for i in range(len(nums) + 1)]

        for num in nums:
            count[num] = 1 + count.get(num, 0)
        for num, cnt in count.items():
            freq[cnt].append(num)

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

Time & Space Complexity

  • Time complexity: O(n)O(n)
  • Space complexity: O(n)O(n)