Table of contents
No headings in the article.
You can find the link to the problem- here
First solution with bucket sort and time complexity O(n)
class Solution {
public int[] topKFrequent(int[] nums, int k) {
if(nums.length == 1)
return nums;
/**
*
* We are using HashMap to store the frequency of numbers
* We'll use it in the next steps
*/
HashMap<Integer, Integer> numsMap = new HashMap<>();
for(int el: nums) {
numsMap.put(el, numsMap.getOrDefault(el, 0) + 1);
}
/**
*
* We create an array of List<Integer> for storing all elements with a certain frequency
*
*
* If we have more than one element with frequency 2, we'll store those elements
* at index 2 in our List at that index in buckets array.
* We'll repeat the same process for all the possible frequencies, if there are no numbers with a certain
* frequency it's List will just point to null
*
* NOTE -
* The reason for creating an array with a length greater than nums.length is because
* indexing starts from zero but we want to store elements with indexes starting from one and going till
* nums. length, that's why we need the size to be greater by one unit.
*
*/
List<Integer>[] buckets = new ArrayList[nums.length + 1];
for(int el: numsMap.keySet()) {
int freq = numsMap.get(el);
if(buckets[freq] == null)
buckets[freq] = new ArrayList<Integer>();
buckets[freq].add(el);
}
/**
*
* We're looping through our buckets array in reverse to get all the elements
* with highest frequencies first.
*
* Whenever our list for a certain frequency is null we'll just skip it.
* However, if we do find a list with values, we'll add those values to result array
* and increment our index till we exhaust the list of till the index is equal to k
*
*/
int[] result = new int[k];
int index = 0;
for(int freq = buckets.length - 1; freq > 0; freq--) {
if(buckets[freq] == null)
continue;
for(int el: buckets[freq]) {
result[index++] = el;
if(index == k)
return result;
}
}
return result;
}
}
Second solution using Priority Queue, we follow a similar approach by creating a hashmap with elements and their frequencies. After that, we store our elements in a priority queue with the highest frequency elements having the highest priority. Finally, we just assign top k values to our result array and return the result array.
class Solution {
public int[] topKFrequent(int[] nums, int k) {
if(nums.length == 1)
return nums;
HashMap<Integer, Integer> numsMap = new HashMap<>();
for(int el: nums) {
if(numsMap.containsKey(el)) {
int count = numsMap.get(el);
count++;
numsMap.put(el, count);
continue;
}
numsMap.put(el, 1);
}
PriorityQueue<Integer> pq = new PriorityQueue<>((a,b)->numsMap.get(b) - numsMap.get(a));
pq.addAll(numsMap.keySet());
int[] result = new int[k];
for(int i=0; i<k; i++) {
result[i] = pq.remove();
}
return result;
}
}
If someone finds any mistake or any opportunity for improvement please do share in the comments, thank you.