35. Search Insert Position

Search Insert Position

Problem Description

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 inserted in order.

You must write an algorithm with O(log n) runtime complexity.

 

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

 

Constraints:

• 1 <= nums.length <= 104
• -104 <= nums[i] <= 104
• nums contains distinct values sorted in ascending order.
• -104 <= target <= 104

Approach) Brute Force

The brute-force approach here is to do more or less exactly what is described above. We loop through the array’s values, looking for the target. If we find either the target or the first occurrence of an integer higher than the target one (which indicates that that’s where the target would be located), we return the index.

Code:

var searchInsert = function (nums, target) {
    for (let i = 0; i < nums.length; i++) {
        if (nums[i] >= target) {
            return i;
        }
    }
    return nums.length;
};

The downside of this simple solution is that we have to check every number in the array in order to get our answer.

Approach) Binary Search

To speed things up, we can employ the use of a fairly standard binary search. The search will half the available array, look for which side’s range of values contains the target (or integers higher than it), and then discards the other side, before repeating the process. 

This means we keep cutting down the array, checking as little data as possible each time, until we’re left either with the target integer, or the next highest number from it, giving us our answer.

Code:

var searchInsert = function (nums, target) {
    let left = 0;
    let right = nums.length;

    while (left < right) {
        const middle = Math.floor((left + right) / 2);

        if (nums[middle] < target) {
            left = middle + 1;
        } else {
            right = middle;
        }
    }

    return left;
};

Approach) Another Approach

We can iterate each element in the array and check some cases

Case 1: if the target element is the current element then return the index of the current element

Case 2: if the target element is smaller than the current element and current element is the first element in the input array then return the index of the current element

Case 3: if the target element is greater than the current element and smaller than the next element then return the current element index +1 since we need to insert the element in the current and next element.

Case 4: if the current element is the last element in the input array and the target is greater than it then the index would be the nums.length & return it

Data Structure & Complexity:

we just use it to store the index and don't use any data structure to store our output, input is an array and we just check elements at each index and don't modify the input.

Time complexity = O(n) we just need one pass for the loop, n is the length of the input array
Space complexity = constant space, we just use a variable for storing an index

Code:

var searchInsert = function (nums, target) {
   let result = 0;
        
        if(nums.length==1 && target>nums[0]){
            return 1;
        }
        
        for(let i=0;i<nums.length-1;i++){
            if(target == nums[i]){
                result =  i;
                break;
            }else if(target>nums[i] && target<=nums[i+1]){
                result = i+1;
                break;
            }else if(target>nums[i+1] && (nums.length-1==i+1)){
                result= nums.length;
                break;
            }else if(target<nums[i] && i==0){
                result =  0;
                break;
            }else if(target>nums[i] && target>nums[i+1]){
                continue;
            }
        }
        
        return result;
        
    }
};

Conclusion

That’s all folks! In this post, we solved LeetCode problem #35. Search Insert Position

I hope you have enjoyed this post. Feel free to share your thoughts on this.

You can find the complete source code on my GitHub repository. If you like what you learn. feel free to fork 🔪 and star ⭐ it.

In this blog, I have tried to collect & present the most critical points to consider when improving Data structure and logic, feel free to add, edit, comment, or ask. For more information please reach me here
Happy coding!