34. Find First and Last Position of Element in Sorted Array

Medium


Given an array of integers nums sorted in non-decreasing order, find the starting and ending position of a given target value.

If target is not found in the array, return [-1, -1].

You must write an algorithm with O(log n) runtime complexity.

 

Example 1:

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

Example 2:

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

Example 3:

Input: nums = [], target = 0
Output: [-1,-1]

 

Constraints:

  • 0 <= nums.length <= 105
  • -109 <= nums[i] <= 109
  • nums is a non-decreasing array.
  • -109 <= target <= 109




 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

        start = self.find_left(nums, target)
        end = -1
        if start != -1:
            end = self.find_right(nums, start, target)

        return [start, end]


    def find_right(self, nums, l, target):
        r = len(nums)-1

        while l <= r:
            mid = l + (r-l)//2

            if nums[mid] == target:
                if mid == r or nums[mid+1] > target:
                    return mid
                else:
                    l = mid+1
            elif nums[mid] > target:
                r = mid - 1
            else:
                l = mid + 1


    def find_left(self, nums, target):

        l, r = 0, len(nums)-1

        while l <=r:
            mid = l + (r-l)//2

            if nums[mid] == target:
                if mid == l or nums[mid-1] < target:
                    return mid
                else:
                    r = mid - 1
            elif nums[mid] > target:
                r = mid - 1
            else:
                l = mid + 1

        return -1

Random Note


From python 3.7 dict guarantees that order will be kept as they inserted, and popitem will use LIFO order but we need FIFO type system. so we need OrderedDict which have popIten(last = T/F) for this req. One thing, next(iter(dict)) will return the first key of the dict