Find the Top K Most Frequent Elements

Given an array, return an array with the top k most frequent elements.

[2, 3, 3, 4, 1, 1, 3], k = 2 => [3, 1]

O(N) Solution (Bucket sort)

The idea here is to use the count of every instance of an element and use it as a bucket. We then read down the elements and see which elements are there. We sacrifice space for time

vector<int> topKMostFreq(vector<int> arr, int k) {
  unordered_map<int, int> elmsToCountMap;
  unordered_map<int, vector<int>> countToElmsMap;
  int largestCount = 0;
  vector<int> ans;

  for(auto i = 0; i < arr.size(); i++) {
    elmsToCountMap[arr[i]]++;
  }

  for(auto elm : elmsToCountMap) {
    countToElmsMap[elm.second].push_back(elm.first);
    largestCount = max(largestCount, elm.second); 
  }

  while(largestCount > 0) {
      if(countToElmsMap.find(largestCount) != countToElmsMap.end()) {
        for(auto i = 0 ; i < countToElmsMap[largestCount].size(); i++) {
          if(k > 0) {
            ans.push_back(countToElmsMap[largestCount][i]);
            k--;
          }
          else {
            break;
          }
        }
      }
    largestCount--;
  }


  return ans;
}