# Top K Frequent Elements

`Heap`, `Sort`

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.

## Analysis

Max Heap

O(N + N log(N-k))

Poll Max Heap when maxheap.size() > hashmap.size() - k

Min Heap

O(N + (N-k)lg k)

Steps

• build a counter map that maps a num to its frequency
• build a heap/priority queue that keeps track of `k` most significant entries
• iterate through the final heap and get the keys

Bucket

O(N)

For [1, 1, 1, 2, 2, 2, 3, 3, 3] and k=2, result=[1,2,3]

## Solution

#### Max Heap

``````// use maxHeap. Put entry into maxHeap so we can always poll a number with largest frequency
public class Solution {
public List<Integer> topKFrequent(int[] nums, int k) {
Map<Integer, Integer> map = new HashMap<>();
for(int n: nums){
map.put(n, map.getOrDefault(n,0)+1);
}

PriorityQueue<Map.Entry<Integer, Integer>> maxHeap =
new PriorityQueue<>((a,b)->(b.getValue()-a.getValue()));
for(Map.Entry<Integer,Integer> entry: map.entrySet()){
}

List<Integer> res = new ArrayList<>();
while(res.size()<k){
Map.Entry<Integer, Integer> entry = maxHeap.poll();
}
return res;
}
}
``````

#### Max Heap 2 - Time: O(Nlog(N - K) + N); Space: O(N)

``````public class Solution {

public List<Integer> topKFrequent(int[] nums, int k) {
List<Integer> res=new ArrayList<>();
if(nums==null||nums.length==0) return res;
Map<Integer,Integer> map=new HashMap<>();
for(int num:nums){                  //count frequency
map.put(num,map.getOrDefault(num,0)+1);
}
//maxHeap, Comparator:map.value
PriorityQueue<Integer> pq=new PriorityQueue<>((a,b)->map.get(b)-map.get(a));
for(int key:map.keySet()){
pq.offer(key);
if(pq.size()>map.size()-k)
}
return res;
}
}
``````

#### Min Heap - Time: O(NlogK + N); Space: O(N)

``````public List<Integer> topKFrequent(int[] nums, int k) {
Map<Integer, Integer> counterMap = new HashMap<>();
for(int num : nums) {
int count = counterMap.getOrDefault(num, 0);
counterMap.put(num, count+1);
}

PriorityQueue<Map.Entry<Integer, Integer>> pq = new PriorityQueue<>((a, b) -> a.getValue()-b.getValue());
for(Map.Entry<Integer, Integer> entry : counterMap.entrySet()) {
pq.offer(entry);
if(pq.size() > k) pq.poll();
}

while(!pq.isEmpty()) {
}
return res;
}
``````

#### Bucket

``````// use an array to save numbers into different bucket whose index is the frequency
public class Solution {
public List<Integer> topKFrequent(int[] nums, int k) {
Map<Integer, Integer> map = new HashMap<>();
for(int n: nums){
map.put(n, map.getOrDefault(n,0) + 1);
}

// corner case: if there is only one number in nums, we need the bucket has index 1.
List<Integer>[] bucket = new List[nums.length + 1];
for(int n:map.keySet()){
int freq = map.get(n);
if(bucket[freq] == null)
}

for(int i = bucket.length-1; i>0 && res.size() < k; --i){
if(bucket[i] != null){
}
}

return res;
}
}
``````

#### TreeMap - Time: O(N + NlogM); Space: O(N)

``````// use treeMap. Use freqncy as the key so we can get all freqencies in order
public class Solution {
public List<Integer> topKFrequent(int[] nums, int k) {
Map<Integer, Integer> map = new HashMap<>();
for(int n: nums){
map.put(n, map.getOrDefault(n,0)+1);
}

TreeMap<Integer, List<Integer>> freqMap = new TreeMap<>();
for(int num : map.keySet()){
int freq = map.get(num);
if(!freqMap.containsKey(freq)){
}
}

List<Integer> res = new ArrayList<>();
while(res.size()<k){
Map.Entry<Integer, List<Integer>> entry = freqMap.pollLastEntry();