5. Top K Frequent Elements

#leetcode/347

Problem 🔗

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

Solution

Solution in C++ using a hash map and sort

We start by calculating the frequency of each element of the array, using an hashmap. Next, we push the pair <frequency, number> in a vector, and we sort it in descending order. In this way, we will have the $k$ most frequent elements in the first $k$ positions of the vector.

vector<int> topKFrequent(vector<int>& nums, int k) {
	unordered_map<int, int> map;
	vector<pair<int, int>> vect;
	vector<int> res;

	//calculate the occurrences of each element
	for(int val : nums)
		map[val]++;

	//push the pair <frequency, number> in a vector	
	for(auto pair : map)
		vect.push_back({pair.second, pair.first});

	//sorting the vector in descending order
	sort(vect.begin(), vect.end(), greater<pair<int,int>>());

	//we have the k most frequent elements in the first k positions of the vector
	for(int i = 0; i < k; i++)
		res.push_back(vect[i].second);

	return res;
}

• Time complexity: $O(n\log n)$ (where n is the size of the vector, the time complexity depends on the sort algorithm)
• Space complexity: $O(n)$ (we are storing all the input)

Solution in C++ using bucket sort

Since the max frequence we can get is equivalent to the size of the input, we can use a sort of counting sort algorithm, more precisely the bucket sort algorithm.
In shorts:

1. We start by calculating the frequency of each element of the array, using an hash map.
2. We find the max frequency in the hash map.
3. We create a vector of vector<int> of size max_frequency (< nums.size()), where each element represents a frequency.
4. We iterate over the hash map and we push each element in the vector, at element.frequency - 1 position.
5. We start iterating from the back of the vector and we return the last $k$ elements.

vector<int> topKFrequent(vector<int>& nums, int k) {
	unordered_map<int, int> map;
	vector<int> res;
	int max_freq = 0;

	//calculate the occurrences of each element and find the max frequency in the hash map
	for(int val : nums) {
		map[val]++;
		max_freq = max(max_freq, map[val]);
	}

	//create a vector where each element represents a frequency
	vector<vector<int>> vect(max_freq);

	//iterate over the hash map and push each element in the vector, at element.frequency - 1 position.
	for(auto pair : map)
		vect[pair.second - 1].push_back(pair.first);

	//start iterating from the back of the vector and return the last k elements
	for(int i = vect.size() - 1; i >= 0 && k > 0; i--) {
		int j;
		for(j = 0; j < vect[i].size() && j < k; j++) {
			res.push_back(vect[i][j]);
		}
		k -= j;
	}

	return res;
}

• Time complexity: $O(n)$ (where n is the size of the vector)
• Space complexity: $O(n)$ (we are storing all the input)