347. Top K Frequent Elements

Prompt

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 <= 105
  • -104 <= nums[i] <= 104
  • k is in the range [1, the number of unique elements in the array].
  • It is guaranteed that the answer is unique.

Solutions

Sorted Frequency Map Solution

In C++

vector<int> topKFrequent(vector<int>& nums, int k) {
unordered_map<int, size_t> freq;
for (int num : nums) freq[num]++;
 
	vector<pair<int, int>> sorted_freq(freq.begin(), freq.end());
	sort(
		sorted_freq.begin(), sorted_freq.end(),
		[](const pair<int, int>& a, const pair<int, int>& b) {
			return a.second > b.second;
		}
	);
 
	vector<int> topK(k);
	for (int i = 0; i < k; ++i) topK[i] = sorted_freq[i].first;
	return topK;
}

Explanation

Create a frequency map of the elements of the input array, sort it, and take the first k and create the answer list from it.

Big O Analysis

Time Complexity

The average time complexity is $O(n\log n)$ because of the sorting, and the worst case is $O(n^2)$. Even if we used Quick Select here, which has a better average complexity of $O(n)$, the worst case is still $O(n^2)$.

Auxiliary Space Complexity

The space complexity is $O(n)$

Optimal Frequency Map Solution

In C++

vector<int> topKFrequent(vector<int>& nums, int k) {
	// each num entry has a frequency
	unordered_map<int, size_t> freq_by_num;
	for (int num : nums) freq_by_num[num]++;
 
	// each frequency entry has a list of nums
	auto nums_by_freq = make_unique<vector<int>[]>(nums.size() + 1);
	for (const auto& pair : freq_by_num) {
		nums_by_freq[pair.second].push_back(pair.first);
	}
 
	// empty first k into answer
	vector<int> topK;
	for (int i = nums.size(); i > 0; --i) {
		const auto& curr_vec = nums_by_freq[i];
		if (!curr_vec.empty()) {
			for (const auto& e : curr_vec) {
				topK.push_back(e);
				if (topK.size() == k) return topK;
			}
		}
	}
	return topK;
}

Explanation

The idea here is that we still do a frequency map, but then from that, we create an array of lists of all numbers that had a certain frequency, where the index is equal to the frequency. Kind of like Radix Sort, because we know extra information about the nature of the data, we can abuse that knowledge to “sort” without needed to compare entries. The information that we know in this case is that the maximum frequency is the length of the input array, and the minimum is 0. Based on this principle, we can take the top K from the highest frequency list all the way down to the lowest, stopping when we have taken k elements.

Time Complexity

The time complexity is $O(n)$

Auxiliary Space Complexity

The space complexity is $O(n)$