Watch 10 video solutions for Find First and Last Position of Element in Sorted Array, a medium level problem involving Array, Binary Search. This walkthrough by take U forward has 308,402 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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] <= 109nums is a non-decreasing array.-109 <= target <= 109Problem Overview: Given a sorted array of integers, return the first and last index where a target value appears. If the target does not exist, return [-1, -1]. The challenge is finding both boundaries efficiently without scanning the entire array.
Approach 1: Linear Scan (O(n) time, O(1) space)
The simplest solution walks through the array from left to right. Record the first index where the target appears, then keep updating the last index while the value matches. This works because you examine every element once. The downside is performance: the algorithm runs in O(n) time even though the array is sorted. This approach is useful for understanding the problem but wastes the sorted property of the input.
Approach 2: Modified Binary Search for First and Last Position (O(log n) time, O(1) space)
The array is already sorted, so binary search gives a faster solution. Instead of stopping when the target is found, continue searching to locate the boundaries. Run binary search once to find the leftmost occurrence: when you see the target, move the right pointer left to check for earlier matches. Run binary search again to find the rightmost occurrence: when you see the target, move the left pointer right to check for later matches.
This works because binary search repeatedly halves the search space. Each search takes O(log n), and performing it twice still keeps the complexity at O(log n). Only a few pointer variables are used, so space complexity stays O(1). The technique is common in array problems where duplicates exist and you need boundary indices rather than just presence checks.
Recommended for interviews: Interviewers expect the modified binary search solution with O(log n) time. Mentioning the linear scan shows baseline reasoning, but the optimized boundary search demonstrates that you recognize the sorted property and can adapt binary search to locate ranges rather than single elements.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Linear Scan | O(n) | O(1) | Quick baseline solution or when the array is not guaranteed to be sorted |
| Two Modified Binary Searches (first + last index) | O(log n) | O(1) | Best approach when the array is sorted and duplicates may exist |