In many programming situations, finding the top k most occurring elements in an array is a common task. This is a problem encountered in various scenarios in a dataset for decision-making. In this article, we’ll explore solutions to the Top K Frequent Elements problem using C++, Java, and Python.
What is the Top K Frequent Elements Problem?
In this problem, we have to find the K most frequent elements in an array. In other words, given an array of integers, the task is to identify the K elements that occur most frequently in the array.
Let us understand it with an example:
Array = [1,1,1,2,2,3,4]
K = 2
Output = [1,2]
Element 1 appears 3 times and 2 appears 2 times, these both are the most occurring elements:
Hashmap Approach to Solve It
In the Hashmap approach, we will use a hashmap to store the frequency of each element present in the array, so that we can count the occurrence of each element.
Steps to solve the problem using this approach:
- Firstly we will declare an unordered map to store the frequency of all elements present in the array and run a loop to count the occurrence of each element.
- Now we will convert the hashmap into a vector of pairs for easier sorting using a custom comparator.
- Now we will Sort the vector of pairs based on the second element in descending order
- Now we will Extract the top k frequent elements using a loop on the vector of pairs and iterating it for k times. And push it into our vector.
C++ Code
Below is the C++ program to find the Top K Frequent Elements in an Array using Hashmap approach:
#include<bits/stdc++.h>
using namespace std;
// Function to compare pairs based on the second element (frequency)
static bool cmp(const pair<int, int>& a, const pair<int, int>& b) {
return a.second > b.second;
}
// Function to find the top k frequent elements in the array
vector<int> topKFrequent(vector<int>& nums, int k) {
// Vector to store the result
vector<int> ans;
// Hash map to store the frequency of each number in the array
unordered_map<int, int> mp;
// Step 1: Count the frequency of each number in the array
for (int i = 0; i < nums.size(); i++) {
mp[nums[i]]++;
}
// Convert the hash map to a vector of pairs for easier sorting
vector<pair<int, int>> freqVec(mp.begin(), mp.end());
// Step 2: Sort the vector of pairs based on the second element (frequency)
sort(freqVec.begin(), freqVec.end(), cmp);
// Step 3: Extract the top k frequent elements
for (int i = 0; i < k; i++) {
ans.push_back(freqVec[i].first);
}
// Return the result vector
return ans;
}
// Main function
int main() {
// Input array and value of k
vector<int> nums = {1, 1, 1, 2, 2, 3, 4};
int k = 2;
// Call the function to find the top k frequent elements
vector<int> result = topKFrequent(nums, k);
// Print the result
cout << "Top " << k << " frequent elements: ";
for (int num : result) {
cout << num << " ";
}
// Return 0 to indicate successful completion
return 0;
}Java Code
We can also implement it in Java as well:
import java.util.*;
public class TopKFrequentElements {
// Function to compare pairs based on the second element (frequency)
static class PairComparator implements Comparator<Map.Entry<Integer, Integer>> {
public int compare(Map.Entry<Integer, Integer> a, Map.Entry<Integer, Integer> b) {
return b.getValue().compareTo(a.getValue());
}
}
// Function to find the top k frequent elements in the array
public static int[] topKFrequent(int[] nums, int k) {
// Map to store the frequency of each number in the array
Map<Integer, Integer> frequencyMap = new HashMap<>();
// Step 1: Count the frequency of each number in the array
for (int num : nums) {
frequencyMap.put(num, frequencyMap.getOrDefault(num, 0) + 1);
}
// Convert the map to a list of entries for easier sorting
List<Map.Entry<Integer, Integer>> freqList = new ArrayList<>(frequencyMap.entrySet());
// Step 2: Sort the list of entries based on the second element (frequency)
freqList.sort(new PairComparator());
// Step 3: Extract the top k frequent elements
int[] result = new int[k];
for (int i = 0; i < k; i++) {
result[i] = freqList.get(i).getKey();
}
// Return the result array
return result;
}
// Main function
public static void main(String[] args) {
// Input array and value of k
int[] nums = {1, 1, 1, 2, 2, 3, 4};
int k = 2;
// Call the function to find the top k frequent elements
int[] result = topKFrequent(nums, k);
// Print the result
System.out.print("Top " + k + " frequent elements: ");
for (int num : result) {
System.out.print(num + " ");
}
}
}
Python Code
The Hashmap approach can be implemented with Python as well:
from typing import List
from collections import Counter
# Function to find the top k frequent elements in the array
def top_k_frequent(nums: List[int], k: int) -> List[int]:
# Step 1: Count the frequency of each number in the array
freq_map = Counter(nums)
# Step 2: Convert the Counter to a list of tuples for easier sorting
freq_list = list(freq_map.items())
# Step 3: Sort the list of tuples based on the second element (frequency)
freq_list.sort(key=lambda x: x[1], reverse=True)
# Step 4: Extract the top k frequent elements
result = [num for num, freq in freq_list[:k]]
# Return the result list
return result
# Main function
if __name__ == "__main__":
# Input array and value of k
nums = [1, 1, 1, 2, 2, 3, 4]
k = 2
# Call the function to find the top k frequent elements
result = top_k_frequent(nums, k)
# Print the result
print("Top", k, "frequent elements:", result)Output:
Top 2 frequent elements: [1, 2]Complexity Analysis
The time complexity is O(n + M * log(M) + k) due to iterating through the array (n), sorting the frequency vector (M * log(M)), and extracting the top k elements
The space complexity is O(M) for the frequency map we have used in our approach where M is the number of unique elements in the array
Conclusion
In conclusion, the leetcode problem of finding the top k frequent elements in an array can be efficiently solved using a hashmap approach. By counting the frequency of each element, converting the hashmap into a vector of pairs, and sorting based on frequency, we can easily extract the top k frequent elements.
