DEV Community

Cover image for Finding the Most Frequent Elements in an Array
Alisa Bajramovic
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]++
    }

    //...
}
Enter fullscreen mode Exit fullscreen mode

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)
    //...
}
Enter fullscreen mode Exit fullscreen mode

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])
    //...
}
Enter fullscreen mode Exit fullscreen mode

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]))
    //...
}
Enter fullscreen mode Exit fullscreen mode

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)
}
Enter fullscreen mode Exit fullscreen mode

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

Top comments (1)

Collapse
 
jwally profile image
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));

Enter fullscreen mode Exit fullscreen mode