Leetcode 35: Search Insert Position

The original question can be found here.

The question is asking for a specific target value, if it exists in the array, return the index. Otherwise, return the index position that it should be inserted.

Brute Force

We just iterate through the array and find the first element that is no less than target:

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        for index, element in enumerate(nums):
            if target <= element:
                return index
        return len(nums)

Time Complexity: O(n). Space Complexity: O(1). Even though we know this is not the optimal solution, it’s still good to come up with this solution first and then provide a more optimized one.

Binary Search

If you are not familiar with binary search, please visit my post here. We can definitely use binary search to find the first element that is no less than target:

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        left, right = 0, len(nums) - 1
        while left + 1 < right:
            mid = (left + right) // 2
            if nums[mid] < target:
                left = mid
            else:
                right = mid
        if nums[left] >= target:
            return left
        if nums[right] >= target:
            return right
        return len(nums)

Time Complexity: O(logn). Space Complexity: O(1).