Table of contents
Open Table of contents
Problem
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]
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.
Explanation/Approach
This problem requires us to identify the k
most frequent elements in an array. A combination of a hash table and a heap can efficiently solve this problem.
Hash Table and Heap Approach:
 Hash Table for Frequency Count: Use a hash table to store the frequency of each element in
nums
.  Heap for Top K Elements: Use a minheap (or a priority queue in some languages) to keep track of the top
k
frequent elements.  Building the Heap: Iterate over the hash table and add each elementfrequency pair to the heap. If the heap size exceeds
k
, remove the element with the lowest frequency.  Result: The heap will contain the
k
most frequent elements.
Hash Table and Bucket Sort Approach:
This problem can be efficiently solved by using a hash table for frequency count and a list of lists (bucket sort) to organize elements by their frequencies.
 Hash Table for Frequency Count: Use a hash table to store the frequency of each element in
nums
.  List of Lists for Buckets: Create a list of lists (buckets) where each index corresponds to the frequency, and each bucket contains elements with that frequency.
 Populating the Buckets: Iterate over the frequency hash table and add elements to the corresponding bucket based on their frequency.
 Extracting Top K Elements: Iterate through the buckets in reverse order and extract elements until we have
k
elements.
Solution: Hash Table and Heap
import heapq
class Solution:
def topKFrequent(self, nums: List[int], k: int) > List[int]:
# Frequency count of each element
frequency = {}
for num in nums:
frequency[num] = frequency.get(num, 0) + 1
# Minheap to store the top k frequent elements
min_heap = []
for num, freq in frequency.items():
heapq.heappush(min_heap, (freq, num))
# If the heap size exceeds k, remove the smallest frequency element
if len(min_heap) > k:
heapq.heappop(min_heap)
# Extract the elements from the heap
top_k_elements = [num for freq, num in min_heap]
return top_k_elements
Time and Memory Complexity
The time complexity of this solution is O(n + k log n), where n is the number of elements in nums
. Building the frequency hash table takes O(n), and each heap operation takes O(log n). The space complexity is O(n) to store the frequency of each element.
Explanation
This solution first counts the frequency of each element using a hash table. Then, it uses a minheap to maintain the top k
frequent elements. By popping elements from the heap when its size exceeds k
, we ensure that only the most frequent elements remain. Finally, the elements in the heap are the required k
most frequent elements.
Visual Representation
Consider the input nums = [1,1,1,2,2,3]
and k = 2
.

Frequency Count:
 The frequency count process will create a hash table representing the frequency of each unique number in
nums
.  Frequency Table:
{1: 3, 2: 2, 3: 1}
.
 The frequency count process will create a hash table representing the frequency of each unique number in

Building the Heap:
 We start building the minheap using the frequency count.
 Initially, the heap is empty. We add elements as
(frequency, number)
pairs.  After adding
(3, 1)
, the heap is[(3, 1)]
.  Adding
(2, 2)
, the heap becomes[(2, 2), (3, 1)]
.  When
(1, 3)
is added, the heap would become[(1, 3), (3, 1), (2, 2)]
. Since the heap size now exceedsk
, we pop the smallest element(1, 3)
. The heap is back to[(2, 2), (3, 1)]
.

Result:
 The final heap contains the
k
most frequent elements, which are[(2, 2), (3, 1)]
.  The top
k
elements extracted from the heap are[2, 1]
.
 The final heap contains the
[1,1,1,2,2,3] > Frequency Table: {1: 3, 2: 2, 3: 1}

V
Min Heap

Add (3, 1)  (3, 1) 
Add (2, 2)  (2, 2), (3, 1)
Add (1, 3)  (1, 3), (2, 2), (3, 1) 


V
Pop (1, 3)  (2, 2), (3, 1) 


V
Top K Elements: [2, 1]
Solution: Hash Table and Bucket Sort
class Solution:
def topKFrequent(self, nums: List[int], k: int) > List[int]:
# Frequency count of each element
frequency = {}
for num in nums:
frequency[num] = frequency.get(num, 0) + 1
# Initialize buckets for each possible frequency
buckets = [[] for _ in range(len(nums) + 1)]
for num, freq in frequency.items():
buckets[freq].append(num)
# Extract the top k frequent elements
top_k_elements = []
for i in range(len(buckets)  1, 0, 1):
for num in buckets[i]:
top_k_elements.append(num)
if len(top_k_elements) == k:
return top_k_elements
Time and Memory Complexity
The time complexity of this solution is O(n), where n is the number of elements in nums
, since each element is processed once to build the frequency table and then once more when building the buckets. The space complexity is also O(n) for storing the frequency table and the buckets.
Explanation
This approach uses a hash table to count the frequency of each element. Then, it uses a list of lists, where each list represents a bucket corresponding to a specific frequency. The elements are placed into these buckets based on their frequency. Finally, the buckets are iterated in reverse order to collect the k
most frequent elements.
Visual Representation
Consider the input nums = [1,1,1,2,2,3]
and k = 2
.

Frequency Count:
 The frequency count process will create a hash table:
{1: 3, 2: 2, 3: 1}
.
 The frequency count process will create a hash table:

Buckets Formation:
 Create buckets for each possible frequency. For our example, since the maximum frequency is 3, we create 4 buckets (including one for frequency 0, which remains empty).
 Bucket 1:
[3]
 Bucket 2:
[2]
 Bucket 3:
[1]

Extracting Top K Elements:
 Start from the highest frequency bucket and move downwards.
 From Bucket 3, pick
[1]
.  From Bucket 2, pick
[2]
.  We have our top
k
elements[1, 2]
.
[1,1,1,2,2,3] > Frequency Table: {1: 3, 2: 2, 3: 1}

V
Buckets Formation

Bucket 3: [1] 
Bucket 2: [2]  Bucket 1: [3]


V
Top K Elements: [1, 2]