Table of Contents
Problem Statement
In top K frequent elements we have given an array nums[], find the k most frequently occurring elements.
Examples
nums[] = {1, 1, 1, 2, 2, 3}
k = 21 2
nums[] = {1}
k = 11
Naive Approach for Top K Frequent Elements
- Build a map of element and frequency by traversing in the given array.
- Sort the entries of the map according to the decreasing order of frequency.
- The first k elements of the sorted map contribute to the answer.
Example
nums[] = {1, 1, 2, 3, 3, 3, 4} and k = 2
Build map of elements and frequency
map = {(1, 2), (2, 1), (3, 3), (4, 1)}
Sort the map in decreasing order of frequency
sorted map = {(3, 3), (1, 2), (2, 1), (4, 1)}
First k entries contributes to the answer
ans = 3 1
Code
Java Code for Top K Frequent Elements
import java.util.*;
class TopKFrequentElements {
private static void printKFrequent(int[] nums, int k) {
// Length of nums array
int n = nums.length;
// Build the map from nums array
HashMap<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < n; i++) {
if (map.containsKey(nums[i])) {
map.put(nums[i], map.get(nums[i]) + 1);
} else {
map.put(nums[i], 1);
}
}
// Sort the map, according to decreasing order of frequency and store in a set
TreeSet<Element> set = new TreeSet<>(new Comparator<Element>() {
@Override
public int compare(Element o1, Element o2) {
return Integer.compare(o2.freq, o1.freq);
}
});
for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
Element curr = new Element(entry.getKey(), entry.getValue());
set.add(curr);
}
// First k elements of the sorted map contributes to the answer
int index = 0;
for (Element element : set) {
System.out.print(element.value + " ");
index++;
if (index == k)
break;
}
System.out.println();
}
public static void main(String[] args) {
// Example 1
int nums[] = new int[]{1, 1, 1, 2, 2, 3};
int k = 2;
printKFrequent(nums, k);
// Example 2
nums = new int[]{1};
k = 1;
printKFrequent(nums, k);
}
// class representing a element and value pair
static class Element {
int value;
int freq;
public Element(int value, int freq) {
this.value = value;
this.freq = freq;
}
}
}C++ Code for Top K Frequent Elements
#include <bits/stdc++.h>
using namespace std;
// structure representing a element and value pair
struct Element {
int value;
int freq;
Element(int v, int f) {
value = v;
freq = f;
}
};
// Comparator to sort elements according to decreasing order of frequency
struct ElemetComp {
bool operator()(const Element &e1, const Element & e2) {
return (e2.freq < e1.freq);
}
};
void printKFrequent(int *nums, int k, int n) {
// Build the map from nums array
unordered_map<int, int> map;
for (int i = 0; i < n; i++) {
if (map.find(nums[i]) == map.end()) {
map.insert(make_pair(nums[i], 1));
} else {
map[nums[i]] = map.find(nums[i])->second + 1;
}
}
// Sort the map, according to decreasing order of frequency and store in a set
set<Element, ElemetComp> set;
unordered_map<int, int>:: iterator itr;
for (itr = map.begin(); itr != map.end(); itr++) {
Element curr(itr->first, itr->second);
set.insert(curr);
}
// First k elements of the sorted map contributes to the answer
int index = 0;
for (auto it = set.begin(); it != set.end(); it++) {
cout<<it->value<<" ";
index++;
if (index == k)
break;
}
cout<<endl;
}
int main() {
// Example 1
int nums[] = {1, 1, 1, 2, 2, 3};
int k = 2;
printKFrequent(nums, k, 6);
// Example 2
int nums2 = {1};
k = 1;
printKFrequent(nums, k, 1);
return 0;
}Complexity Analysis
Time Complexity
O(N * log(N)), cause we have used a map. And map takes log N time for insertion of elements.
Space Complexity
O(N), here we are inserting the elements into the map, which is responsible for this space. Since we inserted N elements, the space complexity is also O(N). Here, N denoted the number of distinct elements. In the worst-case, all numbers might be distinct.
Optimal Approach for Top K Frequent Elements
A better approach is to make a max heap of the element and frequency, according to frequency, removing the top of heap k times gives the answer.
- Build a map of element and frequency by traversing in the given array.
- Build a max heap according to frequency from the map.
- Remove the top of heap k times and this is the answer.
Code for Top K Frequent Elements
Java Code
import java.util.*;
class TopKFrequentElements {
private static void printKFrequent(int[] nums, int k) {
// Length of nums array
int n = nums.length;
// Build the map from nums array
HashMap<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < n; i++) {
if (map.containsKey(nums[i])) {
map.put(nums[i], map.get(nums[i]) + 1);
} else {
map.put(nums[i], 1);
}
}
// Construct a max heap of element and frequency according to frequency
PriorityQueue<Element> heap = new PriorityQueue<>(new Comparator<Element>() {
@Override
public int compare(Element o1, Element o2) {
return Integer.compare(o2.freq, o1.freq);
}
});
// Build heap
for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
heap.add(new Element(entry.getKey(), entry.getValue()));
}
// First k elements of heap contributes to the answer
for (int i = 0; i < k; i++) {
System.out.print(heap.poll().value + " ");
}
System.out.println();
}
public static void main(String[] args) {
// Example 1
int nums[] = new int[]{1, 1, 1, 2, 2, 3};
int k = 2;
printKFrequent(nums, k);
// Example 2
nums = new int[]{1};
k = 1;
printKFrequent(nums, k);
}
// class representing a element and value pair
static class Element {
int value;
int freq;
public Element(int value, int freq) {
this.value = value;
this.freq = freq;
}
}
}C++ Code
#include <bits/stdc++.h>
using namespace std;
// structure representing a element and value pair
struct Element {
int value;
int freq;
Element(int v, int f) {
value = v;
freq = f;
}
};
// Comparator to sort elements according to decreasing order of frequency
struct ElementComp {
bool operator()(const Element &e1, const Element & e2) {
return (e1.freq < e2.freq);
}
};
void printKFrequent(int *nums, int k, int n) {
// Build the map from nums array
unordered_map<int, int> map;
for (int i = 0; i < n; i++) {
if (map.find(nums[i]) == map.end()) {
map.insert(make_pair(nums[i], 1));
} else {
map[nums[i]] = map.find(nums[i])->second + 1;
}
}
// Construct a max heap of element and frequency according to frequency
priority_queue<Element, vector<Element>, ElementComp> heap;
for (auto itr = map.begin(); itr != map.end(); itr++) {
Element element(itr->first, itr->second);
heap.push(element);
}
// First k elements of heap contributes to the answer
for (int i = 0; i < k; i++) {
Element curr = heap.top();
heap.pop();
cout<<curr.value<<" ";
}
cout<<endl;
}
int main() {
// Example 1
int nums[] = {1, 1, 1, 2, 2, 3};
int k = 2;
printKFrequent(nums, k, 6);
// Example 2
int nums2 = {1};
k = 1;
printKFrequent(nums, k, 1);
return 0;
}Complexity Analysis
Time Complexity
O(k log N + N), here N is the number of elements. Because in the worst-case all of the numbers present in the input might be distinct.
O(log N) factor comes because of the time to insert an element into the max heap or priority queue.
Space Complexity
O(N), because we are storing N elements ion worst-case. The space complexity is linear.