Find First and Last Position of Element in Sorted Array
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.
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]
Constraints:
- 0 <= nums.length <= 105
- -109 <= nums[i] <= 109
numsis a non-decreasing array.- -109 <= target <= 109
Solve it on LeetCode
Approaches
1. Linear Scan
Intuition:
The simplest way to find the first and last positions of a target element in a sorted array is to perform a linear scan. We traverse the array from the beginning to end and record the positions when the target element matches.
Code:
- Time Complexity: O(n) - Because we scan through the entire array once.
- Space Complexity: O(1) - Only a constant amount of extra space is used.
2. Binary Search Twice
Intuition:
To improve efficiency, consider using binary search. By performing two separate binary searches, we can find the first occurrence and the last occurrence of the target element. The key is to tailor the binary search condition to continue searching for the first or last position once a target element is found.
Code:
- Time Complexity: O(log n) - Binary search takes logarithmic time.
- Space Complexity: O(1) - Only a constant amount of extra space is used.
3. Optimized Binary Search
Intuition:
We can further optimize by combining the searches for the first and last occurrence into a single binary search. We check for both conditions in a single run, further reducing complexity in terms of constant factors. This method uses binary search with a twist by utilizing stricter compared conditions.
Code:
- Time Complexity: O(log n) if elements are scattered, but potentially O(n) if all elements are the same and span both sections.
- Space Complexity: O(1) - Only a constant amount of extra space is used.