Problem Description

You are given an array of integers nums that is sorted in non-decreasing order (ascending order, allowing duplicates). Your task is to find the starting and ending positions of a given target value within this array.

The function should return an array of two integers [start, end] where:

• start is the index of the first occurrence of target in the array
• end is the index of the last occurrence of target in the array

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

The key constraint is that your algorithm must achieve O(log n) runtime complexity, which means you need to use a binary search approach rather than a linear scan.

For example:

• If nums = [5,7,7,8,8,10] and target = 8, the output should be [3,4] because 8 appears at indices 3 and 4
• If nums = [5,7,7,8,8,10] and target = 6, the output should be [-1,-1] because 6 is not in the array
• If nums = [1] and target = 1, the output should be [0,0] because the single element at index 0 matches the target

The solution uses Python's bisect_left function twice:

1. First to find the leftmost position where target could be inserted (which gives us the starting position if target exists)
2. Second to find the leftmost position where target + 1 could be inserted (which gives us one position after the last occurrence of target)

If these two positions are the same (l == r), it means target doesn't exist in the array, so we return [-1, -1]. Otherwise, we return [l, r-1] as the range.

Intuition

Since the array is sorted and we need O(log n) complexity, binary search is the natural choice. But the challenge is that we need to find both the first and last occurrences of the target, not just any occurrence.

The key insight is that we can transform this problem into finding two specific boundaries:

1. The leftmost position where target appears (or would appear if inserted)
2. The position right after the last occurrence of target

Think about it this way: if we have an array like [5,7,7,8,8,8,10] and target = 8, we want to find where the "8 section" begins and ends.

For the left boundary, we need to find the first position where a value is greater than or equal to target. This is exactly what bisect_left(nums, target) does - it finds the leftmost valid insertion point for target.

For the right boundary, here's the clever part: instead of directly searching for the last occurrence of target, we search for where target + 1 would be inserted. Why? Because bisect_left(nums, target + 1) will give us the first position where a value is greater than or equal to target + 1, which is exactly one position after the last occurrence of target.

For example, with [5,7,7,8,8,8,10] and target = 8:

• bisect_left(nums, 8) returns 3 (first position of 8)
• bisect_left(nums, 9) returns 6 (first position where we could insert 9, which is right after the last 8)
• So the range is [3, 6-1] = [3, 5]

If the target doesn't exist, both bisect_left(nums, target) and bisect_left(nums, target + 1) will return the same position (where target would be inserted if it existed), making l == r, which tells us to return [-1, -1].

This approach elegantly solves the problem with just two binary searches, maintaining the required O(log n) complexity.

Learn more about Binary Search patterns.

Solution Approach

The solution uses binary search to find both boundaries of the target range efficiently. Here's how the implementation works:

Step 1: Find the left boundary

l = bisect_left(nums, target)

The bisect_left function performs a binary search to find the leftmost position where target should be inserted to maintain sorted order. This gives us:

• If target exists in the array, this returns the index of its first occurrence
• If target doesn't exist, this returns the position where it would be inserted

Step 2: Find the position after the right boundary

r = bisect_left(nums, target + 1)

By searching for target + 1, we find the position where the next larger value would be inserted. This cleverly gives us:

• If target exists, this returns the index right after its last occurrence
• If target doesn't exist, this returns the same position as l

Step 3: Check if target exists and return the result

return [-1, -1] if l == r else [l, r - 1]

• If l == r, it means there's no space between where target would start and where target + 1 would start, indicating target doesn't exist in the array
• If l != r, the target exists, and the range is [l, r-1] where r-1 is the last occurrence

Binary Search Details:

The bisect_left function internally implements binary search with the following logic:

• Maintains two pointers: left = 0 and right = len(nums)
• While left < right:
  • Calculate mid = (left + right) // 2
  • If nums[mid] < target, search right half: left = mid + 1
  • Otherwise, search left half: right = mid
• Returns left as the insertion position

Time Complexity: O(log n) - Two binary searches, each taking O(log n) time

Space Complexity: O(1) - Only using a constant amount of extra space for variables

Example Walkthrough:

For nums = [5,7,7,8,8,10] and target = 8:

1. bisect_left(nums, 8) returns 3 (first index of 8)
2. bisect_left(nums, 9) returns 5 (position after last 8)
3. Since 3 != 5, return [3, 5-1] = [3, 4]

For nums = [5,7,7,8,8,10] and target = 6:

1. bisect_left(nums, 6) returns 1 (where 6 would be inserted)
2. bisect_left(nums, 7) returns 1 (where 7 already exists)
3. Since 1 == 1, return [-1, -1]

Example Walkthrough

Let's walk through a detailed example with nums = [2,2,3,4,4,4,5] and target = 4:

Step 1: Find the left boundary (first occurrence of 4)

Using bisect_left(nums, 4):

• Initial: left = 0, right = 7
• Iteration 1: mid = 3, nums[3] = 4, not less than target, search left half → right = 3
• Iteration 2: mid = 1, nums[1] = 2, less than target, search right half → left = 2
• Iteration 3: mid = 2, nums[2] = 3, less than target, search right half → left = 3
• Terminates with left = 3

So l = 3 (first occurrence of 4 is at index 3)

Step 2: Find the position after the right boundary

Using bisect_left(nums, 5) (searching for target + 1):

• Initial: left = 0, right = 7
• Iteration 1: mid = 3, nums[3] = 4, less than 5, search right half → left = 4
• Iteration 2: mid = 5, nums[5] = 4, less than 5, search right half → left = 6
• Iteration 3: mid = 6, nums[6] = 5, not less than 5, search left half → right = 6
• Terminates with left = 6

So r = 6 (position after the last 4)

Step 3: Determine the result

Since l = 3 and r = 6, we have l != r, meaning target exists. Return [l, r-1] = [3, 5]

Verification: In [2,2,3,4,4,4,5], the value 4 appears at indices 3, 4, and 5, so [3,5] is correct!

Edge Case Example:

For the same array with target = 1 (not in array):

• bisect_left(nums, 1) returns 0 (would insert at beginning)
• bisect_left(nums, 2) returns 0 (where 2 already exists)
• Since 0 == 0, return [-1, -1]

Solution Implementation

Time and Space Complexity

The time complexity is O(log n), where n is the length of the array nums. This is because the algorithm uses two binary search operations via bisect_left(). Each bisect_left() call performs a binary search on the sorted array, which takes O(log n) time. Since we perform two binary searches sequentially (one for target and one for target + 1), the total time complexity is O(log n) + O(log n) = O(log n).

The space complexity is O(1). The algorithm only uses a constant amount of extra space to store the two variables l and r, regardless of the input size. The bisect_left() function itself uses iterative binary search internally, which doesn't require additional space proportional to the input size.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Integer Overflow When Computing target + 1

The Pitfall: When using bisect_left(nums, target + 1) to find the right boundary, if target equals the maximum integer value (e.g., 2^31 - 1 in Python), adding 1 would cause integer overflow in languages with fixed integer sizes. While Python handles arbitrary precision integers, this approach could fail in other languages or when porting the solution.

Example Scenario:

nums = [1, 2, 2147483647, 2147483647]
target = 2147483647  # Maximum 32-bit integer
# target + 1 would overflow in many languages

Solution: Instead of searching for target + 1, use bisect_right(nums, target) which directly finds the rightmost position where target could be inserted:

from bisect import bisect_left, bisect_right

def searchRange(self, nums: List[int], target: int) -> List[int]:
    left_index = bisect_left(nums, target)
    right_index = bisect_right(nums, target)
  
    if left_index == right_index:
        return [-1, -1]
    else:
        return [left_index, right_index - 1]

2. Assuming the Array is Non-Empty

The Pitfall: The original solution doesn't explicitly handle empty arrays. While bisect_left works correctly with empty lists (returning 0), it's a common mistake to forget this edge case when implementing custom binary search.

Example Scenario:

nums = []
target = 5
# Should return [-1, -1]

Solution: Add an explicit check for empty arrays if implementing custom binary search:

def searchRange(self, nums: List[int], target: int) -> List[int]:
    if not nums:  # Handle empty array explicitly
        return [-1, -1]
  
    left_index = bisect_left(nums, target)
    right_index = bisect_left(nums, target + 1)
  
    if left_index == right_index:
        return [-1, -1]
    else:
        return [left_index, right_index - 1]

3. Misunderstanding bisect_left Return Value

The Pitfall: A common misconception is that bisect_left(nums, target) returns -1 when the target is not found. In reality, it returns the insertion position, which could be any valid index from 0 to len(nums).

Example Scenario:

nums = [1, 3, 5, 7]
target = 4
# bisect_left returns 2 (not -1), which is where 4 would be inserted
# Without proper checking, you might incorrectly access nums[2] thinking it's the target

Solution: Always verify that the found position contains the target before using it:

def searchRange(self, nums: List[int], target: int) -> List[int]:
    left_index = bisect_left(nums, target)
  
    # Verify that the target actually exists at the found position
    if left_index >= len(nums) or nums[left_index] != target:
        return [-1, -1]
  
    right_index = bisect_left(nums, target + 1)
    return [left_index, right_index - 1]

4. Implementing Custom Binary Search Incorrectly

The Pitfall: When implementing binary search manually instead of using bisect, common mistakes include:

• Using right = len(nums) - 1 when the logic expects right = len(nums)
• Incorrect mid calculation causing infinite loops
• Wrong comparison operators leading to off-by-one errors

Solution: Stick to a consistent binary search template:

def find_left_boundary(nums, target):
    left, right = 0, len(nums)
    while left < right:
        mid = left + (right - left) // 2  # Prevents overflow
        if nums[mid] < target:
            left = mid + 1
        else:
            right = mid
    return left

def find_right_boundary(nums, target):
    left, right = 0, len(nums)
    while left < right:
        mid = left + (right - left) // 2
        if nums[mid] <= target:  # Note the <= for right boundary
            left = mid + 1
        else:
            right = mid
    return left