Problem Statement in English

You’re given an array of integers nums sorted in non-decreasing order, and a target value target. Your task is to 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].

Approach

If you’re using the bisect module, you can use bisect_left to find the leftmost index of the target and bisect_right to find the rightmost index. If the target is not found, you can return [-1, -1].

If you’re hand-rolling the solution, you can implement a binary search with an extra parameter to determine whether to search for the left or right bound of the target. This way, you can find both the starting and ending positions of the target in the array.

If you’re searching for the left bound, you can continue searching to the left even after finding the target. If you’re searching for the right bound, you can continue searching to the right after finding the target.

And we’re done!

Solution in Python

  • Hand Rolled

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        def find_bound(is_first: bool) -> int:
            l, r = 0, len(nums) - 1
            bound = -1
            
            while l <= r:
                mid = (l + r) // 2
                if nums[mid] == target:
                    bound = mid
                    # Keep searching left or right to find the true edge
                    if is_first:
                        r = mid - 1
                    else:
                        l = mid + 1
                elif nums[mid] < target:
                    l = mid + 1
                else:
                    r = mid - 1
                    
            return bound

        left = find_bound(is_first=True)
        if left == -1:
            return [-1, -1]
        
        right = find_bound(is_first=False)
        return [left, right]
  • Using the bisect module

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        if not nums: return [-1, -1]

        l = bisect_left(nums, target)
        r = bisect_right(nums, target) - 1

        if l >= len(nums) or nums[l] != target: l = -1
        if r >= len(nums) or nums[r] != target: r = -1

        return [l, r]

Complexity

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

  • Space: $O(1)$
    Since we are using a constant amount of space for variables and not using any additional data structures that grow with input size, the space complexity is constant.

And we are done.