## DEV Community 👩‍💻👨‍💻 is a community of 966,904 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

Alisa Bajramovic

Posted on

# Finding the Most Frequent Elements in an Array

Today's algorithm is the Top K Frequent Elements problem:

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

For example, if you were given the array `[1, 1, 1, 2, 2, 3, 3, 3]`, and `k = 2`, you'd want to return the two most frequently found elements in the array, which is `[1, 3]`.

This problem has a number of ways to solve it, and many solutions use complex algorithms or sorting techniques. In this post, I'll use commonly found methods to solve this problem. I'll start by discussing how I'll approach the algorithm, and then will code the solution in JavaScript.

## Approaching the Problem

Many times, when algorithms are based on the frequency of an element, it's a good opportunity to use a hash. A hash is so convenient because it stores key-value pairs, where keys can be the element, and the value is its frequency.

In this algorithm, we'll create a hash which will store the frequency of each element in the inputted array. We will then use the `Object.entries()` method, which will turn each key-value pair in the hash into an array of arrays. For example, if the given hash were `{ '1': 3, '2': 2, '3': 3 }`, calling `Object.entries()` and passing in the hash would give us `[ [ '1', 3 ], [ '2', 2 ], [ '3', 3 ] ]`. You can read more about `Object.entries()` here.

With this array, we can then sort it by frequency, and ultimately return the first `k` numbers in the sorted array.

## Coding the Solution

We'll start by initializing an empty object, called `hash`. We'll then want to go through each element in the `nums` array and add it to `hash`. If the element has already been seen in `hash`, then we can increment its value. Otherwise, we can initialize it to 0.

There are many ways to iterate through an array, and in this solution I'll use a for...of loop. You can read more about them here.

``````function topKFrequent(nums, k) {
let hash = {}

for (let num of nums) {
if (!hash[num]) hash[num] = 0
hash[num]++
}

//...
}
``````

For problems like this, I think it's helpful to stop every so often and see what the variables equal at each point. If we were given `nums = [1, 1, 1, 2, 2, 3, 3, 3]`, then at this point, `hash = { '1': 3, '2': 2, '3': 3 }`. You may notice that each key in the hash is a string--that'll be an important thing to correct in a later step.

For now, we want to turn `hash` into an array of arrays, using `Object.entries()`, as discussed above. We'll save the value to a variable called `hashToArray`.

``````function topKFrequent(nums, k) {
let hash = {}

for (let num of nums) {
if (!hash[num]) hash[num] = 0
hash[num]++
}

const hashToArray = Object.entries(hash)
//...
}
``````

Using the same example, where `nums = [1, 1, 1, 2, 2, 3, 3, 3]`, at this point, `hashToArray = [ [ '1', 3 ], [ '2', 2 ], [ '3', 3 ] ]`. Now, we want to sort the elements in `hashToArray`. The first value (index 0) in each inner hash is the element in `nums`. The second value (index 1) in each inner hash is how many times that element was found in `nums`. Therefore, since we want to find the most frequent elements, we'll need to sort `hashToArray`, from most frequently found to least frequently found.

We can use `.sort()`, and sort each inner array by the value at index 1. In other words, we'll pass in the callback function `(a,b) => b[1] - a[1]`. We'll store this sorted array in a variable called `sortedArray`.

``````function topKFrequent(nums, k) {
let hash = {}

for (let num of nums) {
if (!hash[num]) hash[num] = 0
hash[num]++
}

const hashToArray = Object.entries(hash)
const sortedArray = hashToArray.sort((a,b) => b[1] - a[1])
//...
}
``````

Continuing with the same example, where `nums = [1, 1, 1, 2, 2, 3, 3, 3]`, at this point, `sortedArray = [ [ '1', 3 ], [ '3', 3 ], [ '2', 2 ] ]`. Now, for the solution, all we want to return are the most frequently found elements--we don't need to return how many times each element was found. Therefore, we only want the elements at index 0 in `sortedArray`.

As mentioned above, the elements at index 0 are all strings, and we need to return integers. Therefore, we'll use `parseInt`, which converts a string to an integer, and pass in the numbers at index 0 of each inner array in `sortedArray`.

We'll want to store these sorted elements in a new array, which we will call `sortedElements`. We'll call `.map()` on `sortedArray`, and tell it to return the integer version of the first element in each inner array of `sortedArray`.

``````function topKFrequent(nums, k) {
let hash = {}

for (let num of nums) {
if (!hash[num]) hash[num] = 0
hash[num]++
}

const hashToArray = Object.entries(hash)
const sortedArray = hashToArray.sort((a,b) => b[1] - a[1])
const sortedElements = sortedArray.map(num => parseInt(num[0]))
//...
}
``````

At this point, if `nums = [1, 1, 1, 2, 2, 3, 3, 3]`, then `sortedElements = [1, 3, 2]`. We're so close! All that's left to do is to return the first `k` elements of this array. To do that, we'll use `.slice()`, passing in 0 and `k`. We will return this sliced off ported of `sortedElements`, giving us the final result.

``````function topKFrequent(nums, k) {
let hash = {}

for (let num of nums) {
if (!hash[num]) hash[num] = 0
hash[num]++
}

const hashToArray = Object.entries(hash)
const sortedArray = hashToArray.sort((a,b) => b[1] - a[1])
const sortedElements = sortedArray.map(num => parseInt(num[0]))
return sortedElements.slice(0, k)
}
``````

Let me know if you have any questions or other ways you'd solve this problem!

Justin Wolcott

Thanks for sharing this!

I recently got this question during an interview, and my initial solution worked - but was "sub-optimal".

Below is my "refactored" version. It keeps track of the item's count in an object in a sortable array, which saves you from having to use Object.entries.

A minor speedup, but I thought it was clever and worth sharing.

``````//
// NOVEL Function to return the {{k}} most frequent items
// in a javascript array (of strings or numbers) by SIMULTANEOUSLY
// tracking count in a "lookup" object ** AND ** a sortable "output"
// array
//
// Arguments:
// - items: an array of strings or numbers [1,3,500,2,1,3]
// - k: the number of results you want returned
//
// Returns:
// - an array of the top {{k}} most frequent items
//

//
// ALGORITHM APPROACH:
//
// 1.) Create an "output" ary like this: []
//
// 2.) Create a "lookup" object like this: {}
//
// 3.) Iterate over the array of items.
//
//     3a.)   If the item does not exist in our "lookup" object
//            create the following object in the "lookup" object with {{item}} as key
//            {id: item, count: 0}
//
//            *** CRITICAL *** PUSH the object you just created into our "output" array
//            by setting reference to the object in the "lookup" object
//
//      3b.)  When you update the count-attribute of the object in the "lookup" object,
//            it AUTOMAGICALLY updates in the "output" array!
//
// 4.) Sort the "output" array descending on its "count" attribute
//
// 5.) Slice to return the "k" top elements of the output array
//
//
function mostFrequent(items, k){

var lookup = {};
var output = [];
var itemCounter = 0;

for(var i = 0; i < items.length; i++){

// Have we seen this item before or not?
if(!lookup[items[i]]){
// No? Ok, create an object in our lookup
// and set reference to it in our output array
lookup[items[i]] = {"count": 0, "id": items[i]};
output.push(lookup[items[i]]);
itemCounter++;
}

// Add one to the "count" attribute in our lookup
// which adds one to the count attribute in our "output" array
lookup[items[i]].count++;

}

//
// Sort descending, Slice the top {{k}} results, and return it to the user
// so they can handle it
//
return output.sort((a,b) => {return a.count > b.count ? -1 : 1}).slice(0,k)

}

//
// DEMO:
//
console.log(mostFrequent(Array.from({length: 1564040}, () => Math.floor(Math.random() * 40)),4));

``````

This post blew up on DEV in 2020:

## 🚀⚙️ JavaScript Visualized: the JavaScript Engine

As JavaScript devs, we usually don't have to deal with compilers ourselves. However, it's definitely good to know the basics of the JavaScript engine and see how it handles our human-friendly JS code, and turns it into something machines understand! 🥳

Happy coding!