Problem Statement in English

You’re given a sorted array of distinct integers nums and a target value target. Return the index if the target is found. If not, return the index where it would be if it were inserted in order.

Approach

Since the array is sorted we can employ a modified binary search.

If mid is lesser than the target, then it’s guaranteed that the target must come after it, so we can move the left pointer to mid + 1. Otherwise, we move the right pointer to mid.

In the end, the left pointer will be at the index where the target should be inserted.

And we’re done!

Solution in Python


class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        l, r = 0, len(nums) - 1

        while l <= r:
            mid = (l + r) // 2
            if nums[mid] < target:
                l = mid + 1
            else:
                r = mid - 1

        return l

Complexity

  • Time: $O(\log n)$
    Since we are using binary search, the time complexity is logarithmic in relation to the size of the input array nums.

  • Space: $O(1)$
    Since we are using a constant amount of space for variables, the space complexity is constant.

Mistakes I Made

My solution was overcomplicated.

And we are done.