JSFeeds: scotch.io - The Ultimate Guide to JavaScript Algorithms: Where Do I Belong

Wednesday, 6 March, 2019 UTC

The Ultimate Guide to JavaScript Algorithms: Where Do I Belong

Summary

It never feels good to be lost and unable to find your way home, or so out of place and unable to fit in. Don’t get confused, this isn’t some dark and twisted literature about some scared lady lost in the dark and searching for redemption.

In this article, we are going to implement an algorithmic solution to the “where do I belong” challenge. We'll explore ways to determine the position of a number in an array based on its value.

What does this entail?

You should already have your development environment setup for this course. Open the cloned repository and inside the Beginner folder, navigate to the whereIBelong folder. Our work for this challenge will be done in here. Make sure to follow along in the index-START.js file.

The Challenge

Return the lowest index at which a value (second argument) i.e **num** should be inserted into an array (first argument) i.e **arr** once it has been sorted. The returned value should be a number. E.g

whereIBelong([1,2,3,4], 1.5) // should return 1 because it is greater than 1(index 0), but less than 2(index 1).

Algorithmic Thinking

In line with the challenge statement, our function would receive two parameters; an array and a value(number).

Our objective is to determine what position the value would hold if added to the array and sorted according to size i.e in ascending order.

As in the case of the example above, when we add 1.5 to the array and sort it in ascending order, we have:

[1,1.5,2,3,4]

Thus, we would return 1 as that is the index at which the specified value exists within the array.

Let's now see ways to do this in JavaScript.

Code Implementation

We’d cover four(4) ways to solve this challenge with each approach clearly broken down and explained in simple terms. They are:

Using a For-loop to find the immediate larger value's position
Using a For-loop to determine the number of smaller values
Using a while loop to count the smaller values
Finding the index of the value directly

Using a For-loop to find the immediate larger value's position

Here, we follow an indirect approach to find the index at which the received value would exist. Rather than find the index of the element directly, we loop through the array to find the immediate larger value.

The logic here is that when the array is sorted in ascending order, we can determine what position the specified value should be injected into, by determining the value that’d be immediately after it in terms of size.

Looking at the challenge sample, we'd see that after sorting the array, the value that is immediately larger than 1.5 is 2. 2 exists at index one in the array. This means that if we were to insert 1.5 into the array it'd hold same position as 2, thus offsetting two by a positive index.

function whereIBelong(arr, num) {
    arr.sort((a, b) => {
        return a - b
    })
    for (var i = 0; i < arr.length; i++) {
        if (arr[i] >= num) {            return i
        }
    }
    return arr.length
}

Above, we start by using the .sort() method to arrange the array values in ascending order. Next, use a for-loop to iterate through the sorted array while comparing each value with the specified number num. If the value is greater than num, we return the value of the iterator i, which is also the index at which the first larger value was found.

In a situation where none of the values are larger, it means that the specified value will come at the end. So we return the length of the array which is also the index of the next position to be filled.

In the next approach, we use a for-loop for iteration but follow a different approach.

Using a For-loop to determine the number of smaller values

Looking at the challenge sample, you will notice that counting the number of smaller values in the array of numbers also gives us the index at which the specified value would be inserted. That is, since there’s only one number smaller than 1.5, 1.5 would be inserted at index one.

function whereIBelong(arr, num) {
    var counter = 0
    for (i = 0; i < arr.length; i++) {
        if (num > arr++[++i]) {
            counter++;
        }
    } 
    return counter
}

In the code snippet above, we use a for-loop to iterate through each value while counting the number of values that are less than the specified number.

At the start, we initialize a counter variable which is used to keep count of the number of smaller values. For each iteration, we check if the specified value num is greater than the current value under evaluation arr[i]. If it is, we increment counter by 1.

At the end, we return counter which holds the number of smaller values i.e the position at which the number is to be inserted.

Using a While Loop

This implementation follows a similar approach as above but with a different syntax. First, we sort the array in ascending order.

Next, we use a while loop to iterate through the array while incrementing the counter each time the specified number num is greater than the current value arr[counter].

function whereIBelong(arr, num) {
    arr.sort((a, b) => {
        return a - b
    })
    let counter = 0;
    while (num > arr[counter]) {
        counter++
    }
    return counter
}

Conclusively, we return the counter.

Finding the index of the value directly

In this final approach, we directly determine the position of the value by using the .indexOf() method.

First, we push the specified number into the array. Next, we sort the elements of the array in ascending order once again.

Finally, we call the .indexOf() method on the array while passing in the specified value in order to determine the position of the specified value within the array.

function whereIBelong(arr, num) {
    arr.push(num)
    arr.sort((a, b) => a - b)
    return arr.indexOf(num)
}

Notice that we use an arrow function and implicit return statement within the .sort() method. You may learn more about the use of arrow functions and implicit return in this article.

Now to the testing phase!

Testing Testing Correctness with Jest

To execute the tests for this challenge, run the command below:

npm run test whereIBelong

For-loop(finding the immediate larger value)
For-loop(counting the smaller values)
While Loop
Finding the index of the array

We pass all tests. 💪

Testing Performance with JSPerf

Here on JSPerf, we run a performance comparison of the various implementations above. The screenshot below reveals the result:

The best performing implementation as shown above is the use of a for-loop to count the smaller values. All other solutions considered are over 90% slower as noticed in the screenshot.

Practical Application

This challenge is mostly encountered in JavaScript interviews and is also a part of the FreeCodeCamp algorithm scripting challenges.

Conclusion

In this challenge, we have considered four(4) ways to implement the where i belong algorithm. Using JSPerf we have also determined the best performing solution to be the use of a for-loop to determine the number of smaller values in the array.

This marks the last of our array manipulation challenges as we will move into more mathematical challenges from this point forward.

... more @ scotch.io

scotch.io