We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Find First and Last Position of Element in Sorted Array

Difficulty: Medium

Problem Description

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.

Key Insights

  • The array is sorted, which allows the use of binary search.
  • We need to find both the first and last occurrence of the target.
  • A binary search can be modified to find the leftmost and rightmost indices of the target.

Space and Time Complexity

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

Solution

To solve the problem, we will use a modified binary search approach. The algorithm will be executed twice:

  1. First to find the leftmost index of the target.
  2. Second to find the rightmost index of the target.

Both searches will take advantage of the sorted property of the array. We will maintain a low and high pointer to narrow down the search space, adjusting the pointers based on the comparisons with the target value.

Code Solutions

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

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

    left_index = findLeftIndex(nums, target)
    right_index = findRightIndex(nums, target)

    if left_index <= right_index:
        return [left_index, right_index]
    return [-1, -1]
← Back to All Questions