LeetCode 34: Find First and Last Position of Element in Sorted Array

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.

Constraints

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

Examples

• 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]

Solution 1: Brute-Force

Thought

The input parameter nums has already been sorted in increasing order. Therefore, the most intuitive approach is to iterate through the entire array from both the start and end separately. Record the index of the first occurrence of a value equal to the target from both ends and return these two indices at the end.

Steps

1. Initialize two pointers, i and j, starting at 0 and len(nums) - 1, respectively.
2. Initialize the variable positions as [-1, -1] to serve as a record for the found index positions.
3. Start by sequentially iterating through the entire nums starting from i. If nums[i] is equal to the target, record the current position i in positions[0] and then break the iteration.
4. For the second iteration, iterate through nums in reverse, starting from j. If nums[j] is equal to the target, record the current position j in positions[1] and then break the iteration.
5. Finally, return positions.

Codes

def search_range(nums: List[int], target: int) -> List[int]:
    i = 0
    j = len(nums) - 1
    positions = [-1, -1]

    while i < len(nums):
        if nums[i] == target:
            positions[0] = i
            break
        i += 1

    while j >= 0:
        if nums[j] == target:
            positions[1] = j
            break
        j -= 1

    return positions

Complexities

• Time Complexity: O(N),  where N represents the length of nums.
• Space Complexity: O(1).

Solution 2: Binary Search

Thought

The prompt mentioning an optimal time complexity of O(log N) strongly suggests the use of binary search, especially considering the task involves finding a target in a sorted array. We can employ binary search twice successively to approach the closest and farthest targets to obtain the final answer.

Steps

1. Initialize the variable positions as [-1, -1] to serve as a record for the found index positions.
2. The first search:
   1. Initialize the left and right pointers to 0 and len(nums) - 1, respectively, to define the search range.
   2. When left is less than or equal to right:
      1. Calculate the mid position as (left + right) // 2.
      2. If nums[mid] is less than the target, move the left pointer left to the position mid + 1.
      3. If nums[mid] is greater than the target, move the right pointer right to the position mid - 1.
      4. If nums[mid] is equal to the target:
         1. As we’re searching for the first occurrence of the target, we need to check if the element before mid (nums[mid - 1]) is also equal to the target. If it is, move the right pointer to position mid - 1 and continue the search.
         2. If not, it means we’ve found the position of the first occurrence of the target. Record it in positions[0] and terminate the search.
3. The second search:
   1. The search logic is identical to the first search. The only difference is that now we’re searching for the position of the last occurrence of the target. When mid points to a position equal to the target and the next position (nums[mid + 1]) is also equal to the target, move the left pointer to position mid + 1 and continue the search.
4. Finally, return positions.

Codes

def search_range(nums: List[int], target: int) -> List[int]:
    positions = [-1, -1]

    # find the first position
    left, right = 0, len(nums) - 1
    while left <= right:
        mid = (left + right) // 2
        if nums[mid] < target:
            left = mid + 1
        elif nums[mid] > target:
            right = mid - 1
        else:
            if mid > 0 and nums[mid - 1] == target:
                right = mid - 1
            else:
                positions[0] = mid
                break

    # find the last position
    left, right = 0, len(nums) - 1
    while left <= right:
        mid = (left + right) // 2
        if nums[mid] < target:
            left = mid + 1
        elif nums[mid] > target:
            right = mid - 1
        else:
            if mid < len(nums) - 1 and nums[mid + 1] == target:
                left = mid + 1
            else:
                positions[1] = mid
                break

    return positions

Complexities

• Time Complexity: O(logN),  where N represents the length of nums.
• Space Complexity: O(1).

References

• LeetCode link: Find First and Last Position of Element in Sorted Array – LeetCode