JavaScript K Most Frequent Elements in Array

Given an array of integers, find the k most frequent elements and return them in an array.

For example, for the array [1, 1, 2, 3, 5, 5, 1], the k = 2 most common elements are [1, 5].

I’ll mention which lines need to be changed to do this for strings.

Solution 1: Hash map and Sorting

We can solve this problem in O(nlog(n)) time.

1. Start by making a frequency counter with JavaScript objects. Use the element as the key and the frequency as the value.
2. Once we have our frequencies, we need to put them in an array for sorting. We use the ‘in’ keyword to iterate through the keys of the frequency object. Each element in the new array is another array with a key-frequency pair.
3. Sort the array by frequency by passing in your comparison function as a callback. If you’re using strings, here’s the place to use the .localCompare() method instead.
4. Iterate through the array and grab the first k elements.

Solution 2: Sorting and Grouping

This solution is still O(nlog(n)), but slightly more expensive.

1. Sort the array, thereby putting matching elements next to each other.
2. Group adjacent elements into new arrays. For example, map [5, 5, 7] to [[5, 5], [7]].
3. Now map the grouped arrays to a key-frequency pair. [[5, 5], [7]] becomes [[2, 5], [1, 7]].
4. Sort the array by frequency.
5. Iterate through the array and grab the first k elements.