Find First And Last Position Of Element In Sorted Array - Leetcode Solution

Problem statement: Given an array of integers nums sorted in ascending order, find the starting and ending position of a given target value in the array. If the target is not found in the array, return [-1, -1].

Solution:

Approach 1: Linear Scan

The most intuitive solution to this problem is to simply iterate over the entire array and find the first index of the target, and then continue iterating until we find the last index. This solution has a time complexity of O(n), where n is the length of the array.

Code:

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        start,end = -1,-1
        for i in range(len(nums)):
            if nums[i] == target:
                if start == -1:
                    start = i
                end = i
        return [start,end]

Approach 2: Binary Search

Since the array is sorted, we can use the Binary Search algorithm to find the first and last occurrence of the target value. First, we perform a regular Binary Search to find the first occurrence of the target, and then search for the last occurrence by performing another Binary Search in the right half of the array. This approach has a time complexity of O(log n), where n is the length of the array.

Code:

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        def binarySearch(nums,target,lower):
            left = 0
            right = len(nums)-1
            result = -1
            while left <= right:
                mid = (left+right)//2
                if nums[mid] == target:
                    result = mid
                    if lower:
                        right = mid - 1
                    else:
                        left = mid + 1
                elif nums[mid] < target:
                    left = mid + 1
                else:
                    right = mid - 1
            return result
        
        first = binarySearch(nums,target,True)
        if first == -1:
            return [-1,-1]
        last = binarySearch(nums,target,False)
        return [first,last]

Time Complexity: O(log n) - Binary Search Algorithm Space Complexity: O(1) - Constant Space Required

Test Cases:

Input: nums = [5,7,7,8,8,10], target = 8 Output: [3,4]

Input: nums = [5,7,7,8,8,10], target = 6 Output: [-1,-1]

1