LeetCode - Search Insert Position

Problem statement

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.

Problem statement taken from: https://leetcode.com/problems/search-insert-position

Example 1:

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

Example 2:

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

Example 3:

Input: nums = [1, 3, 5, 6], target = 7
Output: 4

Example 4:

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

Example 5:

Input: nums = [1], target = 0
Output: 0

Constraints:

- 1 <= nums.length <= 10^4
- -10^4 <= nums[i] <= 10^4
- nums contains distinct values sorted in ascending order.
- -10^4 <= target <= 10^4

Explanation

Brute Force approach

The brute force approach is to linearly iterate over the array and find the index where the target can be inserted.

The solution is easy and quick to implement but it takes O(n) time.

Since the elements are sorted we can use binary search algorithm to find that correct index.

Binary search approach

Algorithm

- set start = 0 and end = N - 1.
- loop while (start <= end)
  - mid = (start + end)/2

  - if target > nums[mid]
    - start = mid + 1
  - else if target < nums[mid]
    - end = mid - 1
  - else
    - return mid

- return start

C++ solution

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int start = 0;
        int end = nums.size()-1;

        while(start <= end){
            int mid = (start + end)/2;

            if(target > nums[mid]){
                start = mid + 1;
            }else if(target < nums[mid]){
                end = mid - 1;
            }else{
                return mid;
            }
        }

        return start;
    }
};

Golang solution

func searchInsert(nums []int, target int) int {
    start := 0
    end := len(nums) - 1

    for start <= end {
        mid := (start + end) / 2

        if target < nums[mid] {
            end = mid - 1
        } else if target > nums[mid] {
            start = mid + 1
        } else {
            return mid
        }
    }

    return start
}

Javascript solution

var searchInsert = function(nums, target) {
    let start = 0, end = nums.length - 1;
    let mid;

    while( start < end ){
        mid = (start + end) / 2;

        if( target < nums[mid] ){
            end = mid - 1;
        } else if( target > nums[mid] ){
            start = mid + 1;
        } else {
            return mid;
        }
    }

    return start;
};

Dry Run

Let's dry-run our algorithm to see how the solution works.

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

Step 1: start = 0
        end = nums.size() - 1
            = 4 - 1
            = 3

Step 2: loop while( start < end )
        0 < 3
        true

        mid = (start + end)/2
            = (0 + 3)/2
            = 3/2
            = 1

        if target < nums[mid]
           5 < nums[1]
           5 < 3
           false
        else if target > nums[mid]
           5 > nums[1]
           5 > 3
           true

           start = mid + 1
                 = 1 + 1
                 = 2

Step 3: loop while( start < end )
        2 < 3
        true

        mid = (start + end)/2
            = (2 + 3)/2
            = 5/2
            = 2

        if target < nums[mid]
           5 < 5
           false
        else if target > nums[mid]
           5 > nums[1]
           5 > 5
           false
        else
          return mid
          return 2

So the answer returned is 2.