35. Search Insert Position - June day 10

June 10, 2020 — 1 Min Read

Link to leetcode problem definition

Given a sorted array 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 may assume no duplicates in the array.

Example 1:

Input: [1,3,5,6], 5
Output: 2

Example 2:

Input: [1,3,5,6], 2
Output: 1

O(N) solution

A very easy problem to start with, requires a simple iteration over the array and to return the index if the value is equal or bigger than target.

Here is a solution for this approach. Time complexity O(N)

class Solution {
    public int searchInsert(int[] nums, int target) {
        for(int i = 0; i < nums.length; i++) {
            if(nums[i] == target || nums[i] > target) {
                return i;
            }

        }
        return nums.length == 0 ? 0 : nums.length;
    }
}

O(logN) solution

As you could have guessed there is a better solution. The key is the ordering in the array, it is sorted! Sorted entry almost always suggests a some kind of binary search approach.

class Solution {
    public int searchInsert(int[] nums, int target) {
        var left = 0;
        var right = nums.length - 1;
        var mid = 0;
        while(left <= right) {
            // this is an easy way to avoid integer 
            // overflows of (left + right) / 2 approach
            mid = left + (right - left) / 2;
            if(nums[mid] == target) {
                return mid;
            }
            
            if(nums[mid] > target) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        
        return left;
    }
}