35. Search Insert Position

Description

The searchInsert function finds the index at which a target value should be inserted into a sorted list nums to maintain the order. If the target value is found in the list, the function returns the index of the target value.

Intuition

To determine the correct position for the target value, we need to traverse the list and compare each element with the target. By checking where the target fits within the existing elements, we can either find its position or determine where it should be inserted.

Approach

1. Initialize Variables: - result: Initialize to 0, this will store the index where the target should be inserted or found.
2. Iterate Through the List: - Use a for loop to traverse the list from the end to the beginning. - Compare each element with the target value: - If the target is greater than the current element, set result to the next index (i + 1) and break the loop. - If the target is equal to the current element, set result to the current index (i) and break the loop.
3. Return Result: - Return the value of result, which represents the correct index for the target value.

Complexity

Time Complexity:

O(n), where n is the number of elements in the list. We may need to traverse the entire list in the worst case.

Space Complexity:

O(1), as we only use a constant amount of extra space for the result variable.

Code

C++

class Solution {
public:
    int searchInsert(vector& nums, int target) {
        int result = 0;
        for (int i = nums.size() - 1; i >= 0; i--) {
            if (target > nums[i]) {
                result = i + 1;
                break;
            }
            if (target == nums[i]) {
                result = i;
                break;
            }
        }
        return result;
    }
};

Python

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        result = 0
        for i in range(len(nums) - 1, -1, -1):
            if target > nums[i]:
                result = i + 1
                break
            if target == nums[i]:
                result = i
                break
        return result

Java

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

JavaScript

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