Top K Frequent Elements

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

• You may assume k is always valid, 1 ≤ k ≤ number of unique elements.
• Your algorithm’s time complexity must be better than O(n log n), where n is the array’s size.
• It’s guaranteed that the answer is unique, in other words the set of the top k frequent elements is unique.
• You can return the answer in any order.

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

const topKFrequent = (nums, k) => {
  const counts = {};
  const sortable = [];
  const result = [];
  
  //get counts n
  for (let num of nums) {
    counts[num] = (counts[num] || 0) + 1;
  }
  console.log(counts);
  
  //index by counts nlogn
  function sortBy (a,b) {
    return b[1] - a[1];
  }
  for (let i in counts) {
    sortable.push([i, counts[i]]);
  }
  sortable.sort(sortBy);
  console.log(sortable);

  //create result
  for (let i=0;i<k;i++) {
    result.push(sortable[i][0]);
  }
  console.log(result);

  return result;
};

Constraints
1) You may assume that K is always valid and that K is less than number of unique elements
What that means is you’re not going to have an input array of 1s and 2s and then it says you turn the top 3 most common elements. That’s because there’s only two types of items in there so you can’t have top 3 most common. Given that constraint, you don’t have to worry about that error checking.
2) Your algorithm’s time complexity must be better than O(n log n), where n is the array’s size.
I’m not too worried about this one because in general we try to go for the most efficient solution anyways but it’s something to keep in mind as well.
3) It’s guaranteed that the answer is unique, in other words the set of the top k frequent elements is unique.
In other words the set of the top K elements is unique. For example if you have an array of 1,1,1,3,3,3,4,4,4 and you want to turn the top two most common items, that’s non unique because since they all occur three times. The constraint is telling us this won’t happen.

These constraints just make a little bit easier for us so we don’t have to deal with those edge cases and you can return the answer in any order.

Approaches
I thought about doing a sort and then going through it to find the max occurrence. If it’s sorted then you can go through it while keeping track of how many repeats there are of each item. If there’s an item that repeats more than the prior max, set the new max to that This would work if it was the most common item but not in this case since we want the top k most common items.

Now what if we looked at the counts of each element, instead of the original array? For example the initial input of 1,1,1,2,2,3,3, if we store those counts as an object they’ll be an object with properties 1,2,3 and the values of the properties would be 3,2,1 respectively. So that gives us the counts and then we can go through that to find K most frequent elements. However when you look at properties of an object they’re not sorted and therefore you can’t use the order of those properties.
How do we get the K most frequent items out of that count object? We do that by converting the count object into an array of key value pairs. This way we can sort by the values and in an array that order is kept. Then we just look at the k starting or ending items, depending on how we sorted the array. If it’s ascending order then we look at the last K items. If it’s descending order we look at the first K items.

Code Breakdown
Let’s look at the code section by section and explain what we’re doing.

  //get counts n
  for (let num of nums) {
    counts[num] = (counts[num] || 0) + 1;
  }

First we create an object with the counts. We could have used a Map data structure as well, but we use a simple object for simplicity. Note the OR part… if counts[num] doesn’t exist, we can’t add 1 to undefined. What that piece of code is doing is, if it doesn’t exist, we pretend it’s 0 and add 1 to that. If it did exist, we use the existing value. The result is then set to counts[num].

  //index by counts nlogn
  function sortBy (a,b) {
    return b[1] - a[1];
  }
  for (let i in counts) {
    sortable.push([i, counts[i]]);
  }
  sortable.sort(sortBy);

Recall in our approach section that we can’t sort or keep track of the order of properties in an object. So we convert to an array of key-value pairs so we can sort it by the count using the callback function sortBy that we pass to our sort function.

  //create result
  for (let i=0;i<k;i++) {
    result.push(sortable[i][0]);
  }

This creates the final result by pushing the key of each key value pair of the sorted array. We want to keep with output specifications and pass back exactly what users of the function expects. Keep in mind that our sortable array has key value pairs of format ([character],[count of that character]). Therefore sortable[i][0] gets the i-th pair and the character of that pair.
Finally we just return the result array.

Complexity
The time complexity is O(n*logn).
1) Getting the counts is O(n) since we go through the array once
2) Indexing by counts is O(n*logn) since we sort the array.
3) Creating the result is O(n) in worse case scenario. Note that it’s typically less. The number of times that for loop runs is the number of different characters you have in your string. Worst case is each character occurs exactly once except one character occurs twice for example. Note that for a very long string, it’s still limited to the # of characters, or 26 iterations.
Therefore O(n*logn) = O(n)+O(n*logn)+O(n)