Let's solve freeCodeCamp's basic algorithm scripting challenge, 'Where do I Belong'.
Starter Code
function getIndexToIns(arr, num) {
return num;
}
getIndexToIns([40, 60], 50);
Instructions
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 it 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).
Tests
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.
Our Approach
Read everything first. Read the instructions clearly, read the starter code we're given, and read the tests and understand what has to be returned.
- The function takes in two arguments, one being an
arr
being an array, second beingnum
, a number. -
arr
's length varies, it contains numbers or is empty (from the test cases). - We have to return a number. This number will be an index of
arr
. We do not want an array or an item within of the array being returned.
Now that we understand what we are given and what we want to output, let's see how we can solve this.
In short, what we want our function to do: sort arr
in order, smallest to largest, evaluate num
and insert the value into arr
.
arr = [1, 2, 3, 4]
num = 1.5
[1, 1.5, 2, 3, 4]
In the above code block, we have arr
, which is already in order from smallest to largest. We have to determine where 1.5 fits in. It is bigger than 0th index and smaller than 1st index so we want to insert it into 1st index.
Our function should be returning 1, the index where num
now sits.
So our first action is to arrange arr
from smallest to biggest. Array's have a built-in method, sort()
, which would be helpful.
The sort()
method may not work how you think it would. From MDN documentation, it takes in an optional argument, compareFunction
.
arr.sort([compareFunction])
If you are trying to sort numbers in order without providing a compareFunction, things can get a little funky.
"If compareFunction is not supplied, all non-undefined array elements are sorted by converting them to strings and comparing strings in UTF-16 code units order. For example, "banana" comes before "cherry". In a numeric sort, 9 comes before 80, but because numbers are converted to strings, "80" comes before "9" in the Unicode order. All undefined elements are sorted to the end of the array."
Quick example:
let arr = [1, 100, 3, 31, 219, 66]
arr.sort()
Result: [ 1, 100, 219, 3, 31, 66 ]
We have to provide the sort()
method with two arguments to be compared in order to get the smallest to biggest order we're looking for.
let arr = [1, 100, 3, 31, 219, 66]
arr.sort((a, b) => a - b)
Result: [ 1, 3, 31, 66, 100, 219 ]
So one hurdle in solving this is complete. We will have to loop through the sorted array, compare if num
is smaller or larger than each index in order to find the right index to insert at.
Before getting to the looping, from reading the tests, we have to deal with handling an empty array as arr
. We want to return a 0
if arr
is empty.
We can run a quick if statement, see if the arr.length
is 0, to return 0.
if (arr.length === 0) return 0;
We can use a for loop on the sorted array and we will have to include an if statement to see where to insert num
. Once we find the correct index, we can use splice()
to insert it.
splice(index, 0 *values to remove*, num)
An edge case which we have to handle is if num
is bigger than any value in arr
, then we would have to insert it at the end. So let's put an else if in our for loop.
Remember, we want to return the index of where num
will be inserted so we will return indexOf(num)
.
Let's write out this loop and if statement in some broken pseudo code (some JS/pseudo code).
function getIndexToIns(arr, num) {
if arr's length is 0
return 0;
sortedArr = arr.sort((a,b) => a - b)
for (let i = 0; i < sortedArr.length; i++) {
if (num >= sortedArr[i] && num <= sortedArr[i + 1)
{
insert num into sortedArr[i + 1]
return index of num in sortedArr
exit
}
else if (num > sortedArr[sortedArr.length - 1])
{
add num to end of sortedArr
return index of num in sortedArr
exit
}
}
}
So, to summarize:
- We check if arr is empty. If it is empty, we return 0 and exit the function
- If
arr
is not empty, we runsort()
to getsortedArr
sorted from smallest to biggest - Run a loop based on
sortedArr
's length. - Check with an if statement,
num
against each index insortedArr
and the next index. If it is true, we runsplice()
to insert it intosortedArr
- We return
indexOf(num)
- If it runs each time and the if statement is not found to be true, it is concluded that
num
is bigger than any value insortedArr
so we runpush()
to add it to the end ofsortedArr
- We return
indexOf(num)
Our Solution [SPOILER: CONTAINS ANSWER]
function getIndexToIns(arr, num) {
if (arr.length === 0) return 0;
let sortedArr = arr.sort((a, b) => a - b);
for (let i = 0; i < sortedArr.length; i++) {
if (num >= sortedArr[i] && num <= sortedArr[i + 1]) {
sortedArr.splice(i + 1, 0, num);
return sortedArr.indexOf(num);
}
else if (num > sortedArr[sortedArr.length - 1]) {
sortedArr.push(num);
return sortedArr.indexOf(num);
}
}
}
Links & Resources
'Where do I Belong' Challenge on fCC
Thank you for reading!
Top comments (1)
Another way: