TopKFrequentElements.java

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


//trival solution is to sort the nums after counting,

//1  keep count of occurences of each element in hashmap
//2. use a heap that is of size k to insert all elements, at end will hold top K most frequenet
//3. Then add to our ans as we pop off the heap, and reverse our answer to get most frequenet words

//n is length of nums array, k # of topfrequent elements we want 
//TC: O(Nlog(k)) because we insert all N elements into heap, which will take O(logk) time for each insertion
//SC: O(N) to store our count map which has each elements frequency 
class Solution {
    public List<Integer> topKFrequent(int[] nums, int k) {
    
        // build hash map : character and how often it appears
    HashMap<Integer, Integer> count = new HashMap();
    for (int n: nums) {
      count.put(n, count.getOrDefault(n, 0) + 1);
    }

    // init heap 'the less frequent element first'. MIN HEAP
    PriorityQueue<Integer> heap =
            new PriorityQueue<Integer>((n1, n2) -> count.get(n1) - count.get(n2));

    // keep k top frequent elements in the heap
    for (int n: count.keySet()) {
      heap.add(n);
      if (heap.size() > k)
        heap.poll();
    }

    // build output list
    List<Integer> top_k = new LinkedList();
    while (!heap.isEmpty())
      top_k.add(heap.poll());
    Collections.reverse(top_k);
    return top_k;
        
    }
}
BEST SOLUTION
bucket sort!!

public List<Integer> topKFrequent(int[] nums, int k) {

  List<Integer>[] bucket = new List[nums.length + 1];
  Map<Integer, Integer> frequencyMap = new HashMap<Integer, Integer>();

  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<Integer> res = new ArrayList<>();

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