Finding the Most Frequent Elements in an Array
Tags: javascript, codenewbie, algorithms, computerscience
Published: 2020-07-17 16:52:35

Today's algorithm is the [Top K Frequent Elements problem](https://leetcode.com/problems/top-k-frequent-elements/):
>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](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Object/entries).

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](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Statements/for...of).

```javascript
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`.

```javascript
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`.

```javascript
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`.

```javascript
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.

```javascript
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!