Categories

# Top K Frequent Elements – Java

Runtime O(nlogn)

```class Solution {
public List<Integer> topKFrequent(int[] nums, int k) {
HashMap<Integer, Integer> times = new HashMap<Integer, Integer>();
for(int i=0; i<nums.length; i++) {
if(times.get(nums[i])!=null) {
times.put(nums[i], times.get(nums[i])+1);
} else {
times.put(nums[i], 1);
}
}
List<Integer> list = new ArrayList<Integer>(times.keySet());
list.sort((a,b)->times.get(b)-times.get(a));
return list.subList(0,k);
}
}```

## Optimized

Runtime O(n)

```class Solution {
public List<Integer> topKFrequent(int[] nums, int k) {
//count the frequency for each element
HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
int max = 0;
for(int num: nums){
if(map.containsKey(num)){
max = Math.max(map.get(num)+1, max);
map.put(num, map.get(num)+1);
}else{
max = Math.max(max, 1);
map.put(num, 1);
}
}

ArrayList<Integer>[] arr = (ArrayList<Integer>[]) new ArrayList[max+1];
for(int i=1; i<=max; i++){
arr[i]=new ArrayList<Integer>();
}

for(Map.Entry<Integer, Integer> entry: map.entrySet()){
int count = entry.getValue();
int number = entry.getKey();
}

List<Integer> result = new ArrayList<Integer>();

for(int j=max; j>=1; j--){
if(arr[j].size()>0){
for(int a: arr[j]){
if(result.size()==k){
return result;
}
}
}
}

return result;
}
}```