Where Do I Belong

In this freeCodeCamp algorithm we'll take a look at how we can dynamically insert a number into an array based upon it's value.

Spec

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

For example, getIndexToIns([1,2,3,4], 1.5) should return 1 because the value or 1.5 is greater than 1 (index 0), but less than 2 (index 1).

Likewise, getIndexToIns([20,3,5], 19) should return 2 because once the array has been sorted it will look like [3,5,20] and 19 is less than 20 (index 2) and greater than 5 (index 1).

Requirements

• getIndexToIns([10, 20, 30, 40, 50], 35) should return 3

• getIndexToIns([10, 20, 30, 40, 50], 35) should return a Number

• getIndexToIns([10, 20, 30, 40, 50], 30) should return 2

• getIndexToIns([10, 20, 30, 40, 50], 30) should return a Number

• getIndexToIns([40, 60], 50) should return 1

• getIndexToIns([40, 60], 50) should return a Number

• getIndexToIns([3, 10, 5], 3) should return 0

• getIndexToIns([3, 10, 5], 3) should return a Number

• getIndexToIns([5, 3, 20, 3], 5) should return 2

• getIndexToIns([5, 3, 20, 3], 5) should return a Number

• getIndexToIns([2, 20, 10], 19) should return 2

• getIndexToIns([2, 20, 10], 19) should return a Number

• getIndexToIns([2, 5, 10], 15) should return 3

• getIndexToIns([2, 5, 10], 15) should return a Number

• getIndexToIns([], 1) should return 0

• getIndexToIns([], 1) should return a Number

Psuedocode

Let's break down the steps we'll take to solve the algorithm.

// Create function that takes two arguments, arr and num
    
    // If the array is empty, return 0
    
    // Sort the array from low to high
    
    // Loop through the array
        // If current iteration of arr is equal to num
        // OR if num is greater than previous iteration AND less than current iteration
        
        // Return the index
        
        // If num is greater than the last value in arr
            // Return the length of arr

Solving the Algorithm

Setting up the function

We can use the boilerplate given to us from freeCodeCamp which will give us a function that accepts 2 arguments, arr and num.

function getIndexToIns(arr, num) {
   // Find my place in this sorted array.
   return num;
}
getIndexToIns([40, 60], 50);

Check if length of arr equals zero

If arr doesn't have any items in it, let's just return 0 because that would be the lowest index that num could be inserted into arr.

function getIndexToIns(arr, num) {
   
   // Check if arr is empty
   if (arr.length === 0) {
		return 0;
   }
   
   return num;
}
getIndexToIns([40, 60], 50);

Sort arr from low to high

Next we can sort arr from low to high using the Arr.sort() method.

Syntax

arr.sort([compareFunction])

From the MDN Docs:

compareFunction: Specifies a function that defines the sort order. If omitted, the array is sorted according to each character's Unicode code point value, according to the string conversion of each element.

Here's another example from MDN showing us how to sort an array of numbers in ascending order:

function compareNumbers(a, b) {
  return a - b;
}

Let's give this a try using an ES6 Arrow Function:

function getIndexToIns(arr, num) {

   // Check if arr is empty
   if (arr.length === 0) {
		return 0;
   }
   
   // Sort arr
   arr.sort((a,b) => {
       return a-b;
   });
   
   return num;
}
getIndexToIns([40, 60], 50);

Loop through arr, checking num

Now that we've sorted arr from low to high, this will give us some sort of order to work with. We know that no matter what, everytime we're working with arr it will be sorted so we can build any subsequent logic around that.

We need to loop over arr and through each iteration we will check the value of num against it.

If num is equal to arr[i], then let's return i which would be the lowest index that which we could insert num into arr. Otherwise, let's check to see if num happens to be greater than the previous iteration - arr[i-1], and less than the current iteration - arr[i]. If so, we can return the current index, or i for short.

function getIndexToIns(arr, num) {

   // Check if arr is empty
   if (arr.length === 0) {
		return 0;
   }
   
   // Sort arr
   arr.sort((a,b) => {
       return a-b;
   });
   
   // Loop through arr
   for (var i = 0; i < arr.length; i++) {
       
       // Check value of num against current iteration of arr
       if (num === arr[i] || num > arr[i-1] && num < arr[i]) {
           return i;
       }
   }
   
   return num;
}
getIndexToIns([40, 60], 50);

Check if num is greater than other values in arr

Within our loop in the previous step we check if num belongs somewhere in the middle of arr, but we don't check if it should belong at the end of arr. Let's make sure we add that and remove the return num at the bottom of our solution:

function getIndexToIns(arr, num) {

   // Check if arr is empty
   if (arr.length === 0) {
		return 0;
   }
   
   // Sort arr
   arr.sort((a,b) => {
       return a-b;
   });
   
   // Loop through arr
   for (var i = 0; i < arr.length; i++) {
       
       // Check value of num against current iteration of arr
       if (num === arr[i] || num > arr[i-1] && num < arr[i]) {
           return i;
       }

       // Check if num belongs at end of arr
       if (num > arr[arr.length - 1]){
          return arr.length;
       }
   }
}
// getIndexToIns([10, 20, 30, 40, 50], 35) // Should return 3
// getIndexToIns([10, 20, 30, 40, 50], 30) // Should return 2
// getIndexToIns([40, 60], 50) // Should return 1
// getIndexToIns([3, 10, 5], 3) // Should return 0
// getIndexToIns([5, 3, 20, 3], 5) // Should return 2
// getIndexToIns([2, 20, 10], 19) // Should return 2
// getIndexToIns([2, 5, 10], 15) // Should return 3
getIndexToIns([], 1) // Should return 0

Try this the code snippet in your browser console.

Final Thoughts

We were able to get through this freeCodeCamp algorithm, "Where Do I Belong", by using a for-loop and the Array.sort() method. Hopefully you found this walkthrough helpful and if you have a solution of your own I'd love to see it!

Shoot me an email at [email protected] with any questions and if you enjoyed this, stay tuned and subscribe below! 👇