Top K Frequent Elements Leetcode Solution
Top K Frequent Elements Leetcode 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 :
Input: nums = [1,1,1,2,2,3], k = 2
Output: [1,2]
Top K Frequent Elements Leetcode Solution :
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.
Example 1:
- Input: nums = [1], k = 1
- Output: [1]
Intuition :
Intution is to make a HashMap and then use arrayList to add highest frequencies and then store k highest frequeny in another list and at last iterate through the map and add key to the answer array using values that we stored in list2.
Approach :
- First we made a hash Map in which we stored elements of array as key and their frequencies as value in map.
- Now we made a arrayList in which we added all the values(i.e frequencies) of elements of array.
- Now we sorted array in reverse order beacuse we need to get k highest frequency elements .
- Now we made another list in which we added frequencies of k elements .
- Now because we need to return answer in an array type so we created an array named : “ans”.And we used a pointer j to keep on adding Key from map to answer array.
Prime Course Trailer
Related Banners
Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription
Code :
C++
Java
Python
C++
class Solution {
public:
vector< int> topKFrequent(vector< int>& arr, int k) {
unordered_map< int, int> map;
for (int i = 0; i < arr.size(); i++) {
map[arr[i]] = map[arr[i]] + 1;
}
vector< int> list;
for (const auto& entry : map) {
list.push_back(entry.second);
}
sort(list.begin(), list.end(), greater< int>());
vector< int> list2(list.begin(), list.begin() + k);
vector< int> ans(list2.size(), 0);
int j = 0;
for (const auto& entry : map) {
if (find(list2.begin(), list2.end(), entry.second) != list2.end()) {
ans[j++] = entry.first;
}
}
return ans;
}
};
Java
class Solution {
public int[] topKFrequent(int[] arr, int k) {
HashMap< Integer, Integer> map = new HashMap<>();
for (int i = 0; i < arr.length; i++) {
map.put(arr[i], map.getOrDefault(arr[i], 0) + 1);
}
ArrayList< Integer> list = new ArrayList<>(map.values());
Collections.sort(list, Collections.reverseOrder());
ArrayList< Integer> list2 = new ArrayList<>(list.subList(0, k));
int[] ans = new int[list2.size()];
int j = 0;
for (var entry : map.entrySet()) {
if (list2.contains(entry.getValue())) {
ans[j++] = entry.getKey();
}
}
return ans;
}
}Python
class Solution:
def topKFrequent(self, arr, k):
frequency_map = Counter(arr)
frequencies = list(frequency_map.values())
frequencies.sort(reverse=True)
top_k_frequencies = frequencies[:k]
result = []
for key, value in frequency_map.items():
if value in top_k_frequencies:
result.append(key)
return result
Get over 200+ course One Subscription
Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others
Login/Signup to comment