Top K Frequent Elements

PROBLEM

Given an integer array nums and an integer k, return the k most frequent elements. You may return the answer in any order.

Example 1

*Input*: nums = [1,1,1,2,2,3], k = 2
*Output*: [1,2]

Example 2

*Input*: nums = [1], k = 1
*Output*: [1]

SOLVING

We’ll use the Bucket Sort method.

Steps

  1. Create a Map to store the frequency of each letters, a Map buckets and the array for the result
  2. Iterate on the string use each letter as key for frequency and increase by one the value
  3. Fill the buckets by using the value of frequency as the key of buckets and add the key of frequency in the value of the bucket
  4. Iterate from the end of buckets:
    1. Iterate on each element in the bucket value:
      • Add this element to result
      • if result length is equal to k return result

Example

With the parameters nums = [1,1,1,2,2,3] and k = 2

  • Second step

    At the end of the second step you should have this

    frequency = {1: 3, 2: 2, 3: 1}

  • Third step

    At the end of the third step you should have this

    buckets = { 1: [3], 2: [2], 3: [1] }

  • Result

    result = [1, 2]

Code

class Solution {
public:
  vector<int> topKFrequent(vector<int> &nums, int k) {
    unordered_map<int, int> frequency;
    vector<int> result;
    map<int, vector<int>> buckets;

    for (int i = 0; i < nums.size(); i++)
      frequency[nums[i]]++;

    for (auto &it : frequency)
      buckets[it.second].push_back(it.first);

    for (auto rit = buckets.rbegin(); rit != buckets.rend(); rit++) {
      for (auto it : rit->second) {
	result.push_back(it);
	k--;
	if (k == 0)
	  return result;
      }
    }
    return result;
  }
};