Problem

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:

1
2

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

Example 2:

1
2

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

Constraints

  • 1 <= nums.length <= 10^5
  • k is in the range [1, the number of unique elements in the array].
  • It is guaranteed that the answer is unique.

Solution

Method 1 - Sorting

We can create a map of number and frequency. Sort the map based on frequency and return first k elements. But the time complexity will be O(n log n). But of course we can do better.

Method 2 - Using HashMap and Min Heap 🥈

We can

  1. Create frequency map - Use a hashmap or dictionary to count the frequency of each unique element in nums.
  2. Create min heap of size k based on frequency and run the map through it.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
    public List<Integer> topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> freq = new HashMap<>(); // Frequency count
        for (int num : nums) {
            freq.put(num, freq.getOrDefault(num, 0) + 1);
        }
        // Using a priority queue (min-heap)
        PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> a[0] - b[0]);
        for (Map.Entry<Integer, Integer> entry : freq.entrySet()) {
            heap.add(new int[]{entry.getValue(), entry.getKey()});
            if (heap.size() > k) heap.poll();
        }
        List<Integer> ans = new ArrayList<>();
        for (int[] pair : heap) ans.add(pair[1]);
        return ans;
    }
}
1
2
3
4
5
6
7
8

class Solution:
	def topKFrequent(self, nums: List[int], k: int) -> List[int]:
	    freq = Counter(nums)  # Frequency count
	    # Using a min-heap to keep the k most frequent elements
	    heap = [(count, num) for num, count in freq.items()]
	    heapq.heapify(heap)
	    ans = heapq.nlargest(k, heap)
	    return [num for _, num in ans]

Complexity

  • ⏰ Time complexity: O(n log k), where n is the size of nums and k is size of min heap.
    • Count the frequency of elements in O(n) using a hashmap.
    • O(n log k) for using min heap
    • O(n + k) using bucket sort.
  • 🧺 Space complexity: O(n), for the hashmap and additional data structures.

Method 3 - Bucket Sort 🏆

We can use array of linked list, where we can bucketize the numbers based on there frequency. The bucket index will be frequency, values will be number added to that bucket. Number of buckets will be = nums.length+1. Why? Because what if all the element occur once, then it is nums.length; Also, 0 for 0 frequency case. This helps in avoiding edge cases, where we need to sometimes do index-1 etc.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

public int[] topKFrequent(int[] nums, int k) {
	List<Integer>[] bucket = new List[nums.length + 1];
	Map<Integer, Integer> frequencyMap = new HashMap<>();

	for (int num : nums) {
		frequencyMap.put(num, frequencyMap.getOrDefault(num, 0) + 1);
	}

	for (int key : frequencyMap.keySet()) {
		int frequency = frequencyMap.get(key);
		if (bucket[frequency] == null) {
			bucket[frequency] = new ArrayList<>();
		}
		bucket[frequency].add(key);
	}

	int[] ans = new int[k];
    int j = 0;
	for (int pos = bucket.length - 1; pos >= 0; pos--) {
		if(bucket[pos] == null) {
			continue;
		}
		List<Integer> currBucket = bucket[pos];
		for(int i =0; i< currBucket.size() && j < k; i++){
			ans[j++] = currBucket.get(i);
		}
	}
	return ans;
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        # Frequency count using Counter
        freq = Counter(nums)  
        # Bucket where index represents frequency
        bucket: List[List[int]] = [[] for _ in range(len(nums) + 1)]  
        
        # Fill the bucket
        for num, count in freq.items():
            bucket[count].append(num)

        # Extract the top k frequent elements
        ans = []
        for i in range(len(bucket) - 1, 0, -1):  # Traverse bucket from high to low frequency
            if bucket[i]:
                ans.extend(bucket[i])  # Add all elements in the current bucket
            if len(ans) >= k:  # Stop when we have enough elements
                return ans[:k]
        return ans

Complexity

  • ⏰ Time complexity: O(n) each to count frequencies, populate the bucket and collect the top k frequent elements.
  • 🧺 Space complexity: O(n) for the frequency map and bucket.