Day 3- Search Insert Position - leetcode - Python3

 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 it were 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

SOLUTION:

                        1.  Time complexity O(n): linear search

class Solution:

    def searchInsert(nums: List[int], target: int) -> int:

        if target in nums:

            return nums.index(target)

        else:

            i=0

            for i in range(len(nums)):

                if target < nums[i]:

                    return i

            return i+1

The logic of the code is as follows:

1. First, it checks if the target value is already present in the given nums list using the if target in nums condition.

2. If the target is present, it returns the index of the target using the nums.index(target) method. This method returns the index of the first occurrence of the target value in the list.

3. If the target is not present in the list, it enters the else block and initializes the variable i to 0.

4. It then enters a for loop that iterates over each element in the nums list. The loop variable is i.

5. Inside the loop, it checks if the target value is less than the current element nums[i] using the condition if target < nums[i].

6. If the target value is less than nums[i], it means that the target should be inserted at the current index i. In this case, it returns i as the index where the target should be inserted.

7. If the target value is greater than or equal to nums[i], it continues to the next iteration of the loop.

8. After the loop completes, it returns i+1 as the index where the target should be inserted. This handles the case where the target value is greater than all the elements in the list, and it should be inserted at the end.

                 2.  Time complexity O(log n): Binary search

The time complexity of the binary search algorithm is O(log n).

class Solution:

    def searchInsert(self,nums: List[int], target: int) -> int:

        if not nums:

            return 0

        else:

            n: int=len(nums)

            l: int=0

            r: int=n-1

            while(l<r):

                mid=l+(r-l)//2 #1+(3-1)/2 = 2-index

                if nums[mid]==target: return mid

                elif target < nums[mid]:

                    r=mid

                else:

                    l=mid+1

            return l+1 if target > nums[l] else l

       

The space complexity of the code is O(1), which means it uses constant space. The space used by the code does not depend on the size of the input nums list or the target. It only uses a few variables (n, l, r, mid, and target) that occupy a constant amount of space regardless of the input size.

1. If the nums list is empty, it means there are no elements to search. In this case, the function returns 0.

2. If the nums list is not empty, the function initializes the variables n, l, and r. n represents the length of the nums list, l represents the lower bound index, and r represents the upper bound index.

3. The code enters a while loop with the condition l < r. This loop continues until the lower bound l becomes greater than or equal to the upper bound r.

4. Inside the loop, the code calculates the middle index mid using the formula mid = l + (r - l) // 2. This finds the midpoint between the lower and upper bounds, ensuring integer division is used.

5. The code then compares the value at the middle index nums[mid] with the target value.

6. If the value at nums[mid] is equal to the target, it means the target is found at index mid. In this case, the function returns mid.

7. If the value at nums[mid] is greater than the target, it means the target should be present in the left half of the search range. The upper bound r is updated to mid, effectively narrowing down the search space to the left half.

8. If the value at nums[mid] is less than the target, it means the target should be present in the right half of the search range. The lower bound l is updated to mid + 1, effectively narrowing down the search space to the right half.

9. After the while loop finishes, it means the target is not present in the nums list. The code checks if the target is greater than the value at index l to determine the correct index to insert the target.

10. If the target is greater than the value at index l, it means the target should be inserted after the value at index l. In this case, the function returns l + 1.

11. If the target is not greater than the value at index l, it means the target should be inserted at or before the value at index l. In this case, the function returns l.