# Top K elements in an array

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

Given an array `[1,1,1,2,2,3]` and `k = 2`, return `[1,2]`.

This question can be solved in multiple ways

Using HashMap and Array
• For each number maintain a count in the map.
• Create a new TreeMap where the key is the count and value is the list of numbers.
• Since TreeMap is sorted, traverse the map to get k elements.
• Time complexity will be O(nlog n) because it is the time complexity of insertion in a TreeMap.

Using PriorityQueue and hashmap
• For each number maintain a count in the map
• build a heap/priority queue that keeps track of k most significant entries
• iterate through the final heap and get the keys
• The time complexity will be O(Nlgk) which is time to empty the queue.
``````public List topKFrequent(int[] nums, int k) {
Map counterMap = new HashMap();
for(int num : nums) {
int count = counterMap.getOrDefault(num, 0);
counterMap.put(num, count+1);
}
PriorityQueue> pq = new PriorityQueue((a, b) -> a.getValue() - b.getValue());
for(Map.Entry entry : counterMap.entrySet()) {
pq.offer(entry);
if(pq.size() > k) pq.poll();
}

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

Using Bucket Sort

• For each number maintain a count in the map
• Create an array where index represents the count and it stores list of numbers having that frequency
• Traverse the above array from the end and get k elements
• Time complexity is O(n)
``````public List topKFrequent(int[] nums, int k) {
List[] bucket = new List[nums.length + 1];
Map frequencyMap = new HashMap();
for (int n : nums) {
frequencyMap.put(n, frequencyMap.getOrDefault(n, 0) + 1);
}
for (int key : frequencyMap.keySet()) {
int frequency = frequencyMap.get(key);
if (bucket[frequency] == null) {
bucket[frequency] = new ArrayList();
}
}

List res = new ArrayList();

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