347. Top K Frequent Elements

Medium

ArrayHash TableDivide and ConquerSortingHeap (Priority Queue)Bucket SortCountingQuickselect

Companies:

Pocket GemsYelp

Answered: Mar 2, 2026

Problem Description

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

Examples

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⁵
-10⁴ <= nums[i] <= 10⁴
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.

Solutions

Complexity Analysis

Time Complexity:

O (n lo g n)

We iterate through the nums array once to build the frequency map, which takes $O(n)$ time. Sorting the frequency map takes $O(m \log m)$ time, where m is the number of unique elements in the array. In the worst case, m can be equal to n (when all elements are unique), leading to $O(n \log n)$ time complexity.

Space Complexity:

O (n)

We use a hash map to store the frequency of each element, which requires $O(n)$ space in the worst case.

In this solution, we first create a frequency map to count the occurrences of each number in the nums array. We then sort this frequency map based on the frequency values in descending order. Finally, we return the keys of the sorted map, which represent the numbers, and slice the first k elements to get the top k frequent elements.

Complexity Analysis

Time Complexity:

O (n lo g k)

We iterate through the nums array once to build the frequency map, which takes $O(n)$ time. We then iterate through the frequency map, which takes $O(m)$ time, where m is the number of unique elements. For each element, we perform a heap operation that takes $O(\log k)$ time. In the worst case, m can be equal to n (when all elements are unique), leading to $O(n \log k)$ time complexity.

Space Complexity:

O (k)

We use a min-heap to store the top k frequent elements, which requires $O(k)$ space. Additionally, we use a hash map to store the frequency of each element, which requires $O(m)$ space, where m is the number of unique elements. In the worst case, m can be equal to n, leading to $O(n)$ space complexity. However, since we only keep track of the top k elements, the overall space complexity is $O(k)$ .

In this solution, we use a min-heap (priority queue) to keep track of the top k frequent elements. We first build a frequency map to count the occurrences of each number. Then, we iterate through the frequency map and push each number along with its frequency into the min-heap. If the size of the heap exceeds k, we remove the smallest element (the one with the lowest frequency). Finally, we extract the numbers from the heap, which represent the top k frequent elements.

Complexity Analysis

Time Complexity:

O (n)

We iterate through the nums array once to build the frequency map, which takes $O(n)$ time. We then iterate through the frequency map to fill the buckets, which takes $O(m)$ time, where m is the number of unique elements. Finally, we iterate through the buckets to collect the top k elements, which takes $O(n)$ time in the worst case (when all elements are unique). Therefore, the overall time complexity is $O(n)$ .

Space Complexity:

O (n)

We use a frequency map to store the count of each number, which takes $O(m)$ space, where m is the number of unique elements. We also use a list of buckets to group numbers by their frequency, which takes $O(n)$ space in the worst case. Therefore, the overall space complexity is $O(n)$ .

In this solution, we use a bucket sort approach to group numbers based on their frequency. We first build a frequency map to count the occurrences of each number. Then, we create a list of buckets where the index represents the frequency and the value is a list of numbers that have that frequency. Finally, we iterate through the buckets in reverse order (from highest frequency to lowest) and add numbers to the result list until we have k elements.

Conclusion

Approach	Time Complexity	Space Complexity	Advantages	Disadvantages
Sorting	$O(n \log n)$	$O(n)$	Simple to understand and implement	⚠️ Does not meet the follow-up requirement of better than $O(n \log n)$
Min-Heap	$O(n \log k)$	$O(k)$	Efficient when k is much smaller than n, meets follow-up requirement	Requires understanding of heap data structure
Bucket Sort	$O(n)$	$O(n)$	Linear time complexity, no sorting or heap overhead, meets follow-up requirement	Requires $O(n)$ extra space for the bucket array

The optimal approach for this problem is Solution 3: Bucket Sort, which achieves $O(n)$ time complexity and $O(n)$ space complexity. This approach leverages the fact that element frequencies are bounded by the array length, using bucket indices to represent frequencies and avoiding any sorting or heap operations entirely.

Solutions

12 lines
1class Solution:
2    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
3        my_dict = defaultdict(int)
4
5        # Create a list to store the frequency of each number: frequency[num] = count
6        for num in nums:
7            my_dict[num] += 1
8
9        # Sort the dictionary by frequency in descending order
10        sorted_dict = dict(sorted(my_dict.items(), key=lambda x: x[1], reverse=True))
11
12        return list(sorted_dict.keys())[:k]

Complexity Analysis

Time Complexity:

O (n lo g n)

Space Complexity:

O (n)

We use a hash map to store the frequency of each element, which requires $O(n)$ space in the worst case.

21 lines
1import heapq
2
3class Solution:
4    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
5        my_dict = defaultdict(int)
6
7        # Create a list to store the frequency of each number: frequency[num] = count
8        for num in nums:
9            my_dict[num] += 1
10
11        min_heap = []
12
13        for num, freq in my_dict.items():
14            heapq.heappush(min_heap, (freq, num))
15
16            # If the heap exceeds size k, remove the smallest element
17            if len(min_heap) > k:
18                heapq.heappop(min_heap)
19
20        # Extract the numbers from the heap
21        return [num for freq, num in min_heap]

Complexity Analysis

Time Complexity:

O (n lo g k)

Space Complexity:

O (k)

lines
1class Solution:
  def topKFrequent(self, nums: List[int], k: int) -> List[int]:
      my_dict = defaultdict(int)
4
      # Create a list to store the frequency of each number: frequency[num] = count
      for num in nums:
          my_dict[num] += 1
8
      # Create a list of buckets where the index represents the frequency and the value is a list of numbers with that frequency
      bucket = [[] for i in range(len(nums) + 1)]
11
      # Fill the bucket with numbers based on their frequency
      for num, freq in my_dict.items():
          bucket[freq].append(num)
15
      res = []
17
      # Iterate through the bucket in reverse order (from highest frequency to lowest) and add numbers to the result list until we have k elements
      for i in range(len(bucket) - 1, 0, -1):
          for num in bucket[i]:
              res.append(num)
22
              if len(res) == k:
                  return res

Complexity Analysis

Time Complexity:

O (n)

Space Complexity:

O (n)

Conclusion

Approach	Time Complexity	Space Complexity	Advantages	Disadvantages
Sorting	$O(n \log n)$	$O(n)$	Simple to understand and implement	⚠️ Does not meet the follow-up requirement of better than $O(n \log n)$
Min-Heap	$O(n \log k)$	$O(k)$	Efficient when k is much smaller than n, meets follow-up requirement	Requires understanding of heap data structure
Bucket Sort	$O(n)$	$O(n)$	Linear time complexity, no sorting or heap overhead, meets follow-up requirement	Requires $O(n)$ extra space for the bucket array

347. Top K Frequent Elements

Problem Description

Examples

Example 1

Example 2

Example 3

Constraints

Follow-up

Solutions

Solution 1: Sorting

Complexity Analysis

Explanation

Solution 2: Min-Heap

Complexity Analysis

Explanation

Solution 3: Bucket Sort

Complexity Analysis

Explanation

Conclusion

347. Top K Frequent Elements

Problem Description

Examples

Example 1

Example 2

Example 3

Constraints

Follow-up

Solutions

Solution 1: Sorting

Complexity Analysis

Explanation

Solution 2: Min-Heap

Complexity Analysis

Explanation

Solution 3: Bucket Sort

Complexity Analysis

Explanation

Conclusion