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!