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();
    }
    
    List res = new LinkedList();
    while(!pq.isEmpty()) {
        res.add(0, pq.poll().getKey());
    }
    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();
		}
		bucket[frequency].add(key);
	}

	List res = new ArrayList();

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