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

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

https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array/

Problem

Given an array of integers nums sorted in non-decreasing order and a target value target, find the first and last position of the target value in the array.

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

You must write an algorithm with O(log n) runtime complexity.

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

This problem requires finding the first and last occurrence of a target value in a sorted array, with a time complexity of O(log n). This can be efficiently solved using binary search.

We can perform two binary searches:

Find the first position:
- When nums[mid] == target, move right to mid - 1 to continue searching for the first occurrence on the left side.
Find the last position:
- When nums[mid] == target, move left to mid + 1 to continue searching for the last occurrence on the right side.

Code Implementation:

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]: 
        # Search for the first occurrence of the target
        def find_first(nums, target):
            l, r = 0, len(nums) - 1 
            idx = -1
            while l <= r: 
                mid = (l + r) // 2
                if nums[mid] >= target:  # Search on the left
                    r = mid - 1
                    if nums[mid] == target:
                        idx = mid  # Update idx, it might be the first occurrence
                else:
                    l = mid + 1
            return idx

        # Search for the last occurrence of the target
        def find_last(nums, target):
            l, r = 0, len(nums) - 1 
            idx = -1
            while l <= r: 
                mid = (l + r) // 2
                if nums[mid] <= target:  # Search on the right
                    l = mid + 1
                    if nums[mid] == target:
                        idx = mid  # Update idx, it might be the last occurrence
                else:
                    r = mid - 1
            return idx

        first = find_first(nums, target)

        if first == -1:  # If target is not found
            return [-1, -1]

        last = find_last(nums, target)

        return [first, last]

Code Explanation:

Find First Occurrence (find_first):
- Use binary search. If nums[mid] >= target, move right to mid - 1 to search on the left side.
- When nums[mid] == target, update idx as a potential first occurrence and continue searching the left side.
Find Last Occurrence (find_last):
- Similarly, use binary search. If nums[mid] <= target, move left to mid + 1 to search on the right side.
- When nums[mid] == target, update idx as a potential last occurrence and continue searching the right side.
Combine Results:
- First, call find_first to find the first occurrence. If it returns -1, the target is not in the array, and return [-1, -1].
- Then, call find_last to find the last occurrence and return [first, last].

Complexity Analysis:

Time Complexity: O(log n), as we perform two binary searches, each taking O(log n) time.
Space Complexity: O(1), since we only use a few extra variables.

Example Walkthrough:

Example 1:

Input: nums = [5,7,7,8,8,10], target = 8

First binary search find_first:
- First iteration: mid = 2, nums[2] = 7, move left to 3.
- Second iteration: mid = 4, nums[4] = 8, move right to 3, idx = 4.
- Third iteration: mid = 3, nums[3] = 8, idx = 3, move right to 2.
- Result: first = 3.
Second binary search find_last:
- First iteration: mid = 2, nums[2] = 7, move left to 3.
- Second iteration: mid = 4, nums[4] = 8, idx = 4, move left to 5.
- Result: last = 4.

Final result: [3, 4].

Example 2:

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

The first binary search find_first:
- Does not find the target, returns -1.

Result: [-1, -1].

Summary

Chinese: 本题通过二分查找方式，分别查找目标值的第一个和最后一个位置，在 O(log n) 时间复杂度下完成任务。

Key Tips:

Binary Search: Efficiently find the first and last position of the target using two separate binary searches.
Edge Conditions: If first == -1, return [-1, -1], indicating the target is not in the array.
Boundary Control: For find_first, move right when nums[mid] >= target. For find_last, move left when nums[mid] <= target.

CODEBITWAVE

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