LeetCode Solutions Blog

Find First and Last Position of Element in Sorted Array

Number: 34

Difficulty: Medium

Paid? No

Problem Description

Given a sorted array of integers and a target value, the goal is to find the starting and ending position of the target value in the array. If the target is not present, return [-1, -1]. The solution must run in O(log n) time.

Key Insights

The array is sorted, allowing the use of binary search.
Two binary searches can efficiently find the leftmost (first) and rightmost (last) indices of the target.
Handling edge cases where the target is not present by checking bounds.

Space and Time Complexity

Time Complexity: O(log n)
Space Complexity: O(1)

Solution

The approach is to use binary search twice:

The first binary search finds the leftmost occurrence of the target by continuing to search in the left half even after finding the target.
The second binary search finds the rightmost occurrence by searching in the right half. The algorithm maintains pointers for the current search bounds and narrows the search space using comparisons. If the target is not found during the first binary search, the solution immediately returns [-1, -1]. This method leverages the sorted property of the array, ensuring O(log n) time complexity with constant extra space.

Code Solutions

def searchRange(nums, target):
    # Helper function to find the boundary index (leftmost or rightmost) for target.
    def findBoundary(isLeft):
        left, right = 0, len(nums) - 1
        boundary = -1
        while left <= right:
            mid = (left + right) // 2
            # If the target is found, update boundary and continue to search on one side.
            if nums[mid] == target:
                boundary = mid
                if isLeft:
                    right = mid - 1  # Continue search on left half
                else:
                    left = mid + 1  # Continue search on right half
            elif nums[mid] < target:
                left = mid + 1
            else:
                right = mid - 1
        return boundary

    # Find the leftmost index
    leftIndex = findBoundary(True)
    if leftIndex == -1:
        return [-1, -1]
    # Find the rightmost index
    rightIndex = findBoundary(False)
    return [leftIndex, rightIndex]

# Example usage:
# nums = [5,7,7,8,8,10]
# target = 8
# print(searchRange(nums, target))  # Output: [3,4]