# Top K Frequent Elements

Given a non-empty array of integers, return the k most frequent elements.

Example 1:

```Input: nums = [1,1,1,2,2,3], k = 2
Output: [1,2]
```

Example 2:

```Input: nums = [1], k = 1
Output: [1]```

Note:

• You may assume k is always valid, 1 ≤ k ≤ number of unique elements.
• Your algorithm’s time complexity must be better than O(n log n), where n is the array’s size.
• It’s guaranteed that the answer is unique, in other words the set of the top k frequent elements is unique.
• You can return the answer in any order.
###### Approach 1: Create a FrequencyMap and Sort by values.
1. Create a `HashMap` out of the array. Where the `key` of the `Map` is the element from `nums` and the `value` is the frequency of each number. This step takes `O(N)` time where `N` is the number of elements in the list.
2. Once the Map is constructed from the array, then We can sort the `HashMap `by values to get the desired result. This step will take `O(NlogN)`
3. If we create the frequency map for the given input and sort it by `values:`
• `Key Value 1 3 2 2 3 1`

Following is the Java Implementation:

```import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

class MapComparator implements Comparator<Map.Entry<Integer, Integer>> {
public int compare(Map.Entry<Integer, Integer> entry1,
Map.Entry<Integer, Integer> entry2) {
return (entry2.getValue() - entry1.getValue());
}
}

class TopKFrequent {
public List<Integer> getTopK(int[] nums, int k) {
Map<Integer, Integer> frequencyMap = new HashMap<>();
for (int num : nums) {
int count = frequencyMap.getOrDefault(num, 0);
frequencyMap.put(num, (count + 1));
}
List<Map.Entry<Integer, Integer>> entryList =
new ArrayList<>(frequencyMap.entrySet());
Collections.sort(entryList, new MapComparator());
List<Integer> result = new ArrayList<>();
for (Map.Entry<Integer, Integer> entry : entryList) {
if (k > 0) {
k--;
} else break;
}
return result;
}
}

public class Solution {
public static void main(String[] args) {
TopKFrequent topKFrequent = new TopKFrequent();
int k = 2;
int[] nums = {4, 1, -1, 2, -1, 2, 3};
List<Integer> result = topKFrequent.getTopK(nums, k);
System.out.println(result);
}
}
```
###### Approach 2: Create a FrequencyMap and MinHeap to track top k elements
1. Create a `HashMap` out of the array. Where the `key` of the `Map` is the element from `nums` and the `value` is the frequency of each number. This step takes `O(N)` time where `N` is the number of elements in the list.
2. The second step is to build a heap. The time complexity of adding an element in a heap is `O(log(k))` and we do it `N` times that means `O(Nlog(k))` time complexity for this step. The last step to build an output list.
```class Element{
int num;
int count;

public Element(int n, int c){
this.num = n;
this.count = c;
}
}

class Solution {
public int[] topKFrequent(int[] nums, int k) {

Map<Integer, Integer> countMap = new HashMap<>();
for(int n : nums){
int frequency = countMap.getOrDefault(n, 0);
countMap.put(n, frequency+1);
}

Queue<Element> minHeap = new PriorityQueue<>(new Comparator<Element>(){

public int compare(Element e1, Element e2){
return Integer.compare(e1.count, e2.count);
}
});

for(int key : countMap.keySet()){
Element element = new Element(key, countMap.get(key));
minHeap.offer(element);
if(minHeap.size() > k){
minHeap.poll();
}
}

int i = 0;
int[] result = new int[k];
for(Element elem : minHeap){
result[i] = elem.num;
i++;
}
return result;
}
}
```

Complexity Analysis

• Time Complexity: `O(Nlog(k))`. The complexity of the Counter method is `O(N)`. To build a heap and output list takes `O(Nlog(k))`. Hence the overall complexity of the algorithm is `O(N+Nlog(k))=O(Nlog(k))`.
• Space Complexity: `O(N)` to store the hash map.

Categories: Heap

Tagged as: