LeetCode #35. Search Insert Position - Sorted Array Problem

Taylor — Tue, 14 Sep 2021 03:36:24 +0000

Hi there, let's solve this problem using JavaScript! I have 2 possible solutions for this problem.

The Problem:

Given a sorted array of distinct integers and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.
You must write an algorithm with O(log n) runtime complexity.

Example:
Input: nums = [1,3,5,6], target = 5
Output: 2

Break it down:

A sorted array - we need to provide an array in ascending order.
Distinct integers and target value - We cannot have multiples of the same number, including the target number if it already exists in the array.
If the target already exists in the array, provide the index location.
If the target is not already in the array, add it to the array and provide the index location.

Solution #1 with comments:


var searchInsert = function (nums, target) {
  //where does the array start, index of[0]
  let startInt = 0;
  //the total length of the array is the end
  let endInt = nums.length;
  //while loop to trigger the search condition
  while (startInt < endInt) {
    //sets a new variable for the middle of the array.
    //Math.floor takes care of odd numbered arrays(rounds down)
    let midInt = startInt + Math.floor((endInt - startInt) / 2);
    //if midInt is equal to target, return target
    if (nums[midInt] === target) {
      return midInt;
      //else if midInt > target, endInt is new midInt.
      //this tells the next iteration to look to the left/start
    } else if (nums[midInt] > target) {
      endInt = midInt;
    } else {
      //midTarget is less than target, increase by 1 till true
      startInt = midInt + 1;
    }
  }
  //finally, startInt is now the target, return results
  return startInt;
};

Solution #2 with comments:

var searchInsert = function (nums, target) {
  //use indexOf array method, get index of target if not false/-1
  if (nums.indexOf(target) !== -1) {
    // if target exists in array, return index of target
    return nums.indexOf(target);
  } else {
    //if target doesn't exist in array, add target to end of array
    nums.push(target);
    //first we sort the array to meet the requirement
    nums.sort((a, b) => a - b);
  }
  // return index location of target
  return nums.indexOf(target);
};

Either of these should do it!

More about the array.sort(compare) function

I wanted to talk a little more about this because it was something new for me and thought it might be helpful.

This method is used to keep sorted arrays as numbers rather than letting it convert into a Unicode values after being sorted. This is important to be able to return the index for the solution.

You may also see this expanded out like this:

nums.sort((a,b) => {
    if(a > b) return 1;
    if(a < b) return -1;
    return 0;
});

Or even further expanded like so:

nums.sort(function(a,b){
    if(a > b) return 1;
    if(a < b) return -1;
    return 0;
});

I found a great explanation of the .sort() method here which also covers sorting an array of strings.