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

Input: The input is a sorted array 'nums' and a target value that needs to be searched.

Example: nums = [1, 2, 3, 3, 3, 5, 6, 7], target = 3

Constraints:

• 0 <= nums.length <= 10^5

• -10^9 <= nums[i] <= 10^9

• nums is sorted in non-decreasing order.

• -10^9 <= target <= 10^9

Output: The output should be an array of two integers, representing the starting and ending position of the target value, or [-1, -1] if the target is not found.

Example: For nums = [1, 2, 3, 3, 3, 5, 6, 7], target = 3, the output is [2, 4].

Constraints:

Goal: To find the starting and ending positions of the target in a sorted array efficiently.

Steps:

• Use binary search to find the first occurrence of the target value (lower bound).

• Use binary search to find the position just after the last occurrence of the target value (upper bound).

• Return the index range or [-1, -1] if the target is not found.

Goal: The solution should work within the given constraints and time complexity.

Steps:

• The array can have up to 10^5 elements.

• The target value can be any integer between -10^9 and 10^9.

Assumptions:

• The array is sorted and can contain duplicate values.

• Input: nums = [1, 2, 3, 3, 3, 5, 6, 7], target = 3

• Explanation: The target value 3 appears three times in the array. The starting position is 2, and the ending position is 4.

• Input: nums = [1, 2, 3, 3, 3, 5, 6, 7], target = 0

• Explanation: The target value 0 is not present in the array, so the output is [-1, -1].

• Input: nums = [], target = 5

• Explanation: The array is empty, so the target cannot be found, resulting in [-1, -1].

Approach: The approach is to utilize binary search to efficiently find the starting and ending positions of the target in the sorted array.

Observations:

• Since the array is sorted, binary search can help find the target in O(log n) time.

• We can use two binary search operations: one for finding the first occurrence and one for finding the last occurrence of the target.

Steps:

• Find the first occurrence of the target using lower bound.

• Find the position just after the last occurrence using upper bound.

• Return the range of indices or [-1, -1] if the target is not found.

Empty Inputs:

• If the array is empty, the result should be [-1, -1].

Large Inputs:

• The algorithm must handle arrays of size up to 10^5 efficiently.

Special Values:

• If the target value is not present in the array, return [-1, -1].

Constraints:

• The solution should run in O(log n) time, so avoid linear searches.

vector<int> searchRange(vector<int>& nums, int target) {
    
    auto it1 = lower_bound(nums.begin(), nums.end(), target);
    auto it2 = upper_bound(nums.begin(), nums.end(), target);

    if(it1 == nums.end() || *it1 != target) return {-1, -1};

    return {(int) (it1 - nums.begin()), (int) (it2 - nums.begin() - 1)};
}

1 : Function Declaration

vector<int> searchRange(vector<int>& nums, int target) {

This line declares a function named 'searchRange' that takes a sorted array 'nums' and a target integer 'target' as input and returns a vector containing the first and last positions of the target element, or {-1, -1} if the target is not found.

2 : Binary Search

    auto it1 = lower_bound(nums.begin(), nums.end(), target);

This line uses the `lower_bound` function to find the first occurrence of the target element in the array. It returns an iterator pointing to the first element greater than or equal to the target.

3 : Binary Search

    auto it2 = upper_bound(nums.begin(), nums.end(), target);

This line uses the `upper_bound` function to find the first element greater than the target element in the array. It returns an iterator pointing to the first element greater than the target.

4 : Conditional Check

    if(it1 == nums.end() || *it1 != target) return {-1, -1};

This line checks if the `lower_bound` iterator points to the end of the array or if the element at the `it1` position is not equal to the target. If either condition is true, it means the target is not found in the array, so the function returns {-1, -1}.

5 : Result Calculation

    return {(int) (it1 - nums.begin()), (int) (it2 - nums.begin() - 1)};

If the target is found, the function returns a vector containing the first and last positions of the target. The first position is calculated by subtracting the beginning iterator of the array from the `it1` iterator, and the last position is calculated by subtracting the beginning iterator from the `it2` iterator and then decrementing by 1.

Best Case: O(log n)

Average Case: O(log n)

Worst Case: O(log n)

Description: The time complexity is O(log n) because we are performing binary search operations.

Best Case: O(1)

Worst Case: O(1)

Description: The space complexity is O(1) because no additional space is required beyond the input array.

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

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

Explore →