[Top Interview 150] 35. Search Insert Position

Solution)

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        # Two Pointers
        left, right = 0, len(nums)-1

        while left <= right:
            # Center Pointer
            center = (left+right) // 2

            # Conditions where center is returned immediately
            if nums[center] == target or nums[center-1] < target < nums[center]:
                return center
            
            else:
                if nums[center] > target:
                    # Reached the start of an array
                    if center == 0:
                        return center

                    # Update right pointer
                    right = center-1

                else:
                    # Reached the end of an array
                    if center == len(nums)-1:
                        return center+1

                    # Update left pointer
                    left = center+1

 
Problem: LeetCode
 
Time Complexity: O(log n)
Space Complexity: O(1)

Explanation)

Since nums is a sorted array, we can use a binary search to effeciently find the target.
 
 

Initialization)

To use a binary search, we'll have two pointers that are placed at the ends of nums.
 

def searchInsert(self, nums: List[int], target: int) -> int:
        left, right = 0, len(nums)-1

 
 

While Loop 1)

Binary search will be executed until the left pointer jumps over the right pointer.
 
center is updated every loop, meaning the searching range of nums is halved every loop.
 
If nums[center] is the same as target, which is the ideal situation, we'll obviously return center. However, nums doesn't always contain target in its array and we have to return an index where that target should be placed.
 
If the array doesn't contain target, the target integer can be placed in-between two adjacent numbers. So I decided to mark that condition as nums[center-1] < target < nums[center].
 

def searchInsert(self, nums: List[int], target: int) -> int:
        left, right = 0, len(nums)-1

        while left <= right:
            center = (left+right) // 2

            if nums[center] == target or nums[center-1] < target < nums[center]:
                return center

 
 

While Loop 2)

Now we'll look at conditions where we cannot find a target and where we cannot put target inbetween two adjacent numbers.
 
If you've done binary search before, you would know that if nums[center] is bigger than target, you need to update right pointer to center - 1 to reduce the searching range into lower half.
 
We need to put one more step for this problem. 
 
There'll be a case where the target is so small that it needs to be placed at the front of the nums. This case is reached when nums[center] is bigger than target and when both left and right pointers are at 0. In this case, we'll return center which is zero.
 
The same goes to when nums[center] is less than target.
 

def searchInsert(self, nums: List[int], target: int) -> int:
        left, right = 0, len(nums)-1

        while left <= right:
            center = (left+right) // 2

            if nums[center] == target or nums[center-1] < target < nums[center]:
                return center
            
            else:
                if nums[center] > target:
                    if center == 0:
                        return center

                    right = center-1

                else:
                    if center == len(nums)-1:
                        return center+1

                    left = center+1

 
 
 
My initial plan was to just focus on LeetCode until I'm done with this study plan. But I really want to study app development and I'm gonna try doing both of them. LeetCode solutions will be usually posted on weekdays and I'll post a weekly article of studying app development. Keeping myself busy helps me stay away from miscellaneous thoughts :)