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 NeetCode has 115,942 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: You are given a sorted integer array and a target value. Return the first and last index where the target appears. If the value does not exist, return [-1, -1]. The challenge is finding both boundaries efficiently rather than scanning the whole array.
Approach 1: Linear Scan (O(n) time, O(1) space)
The straightforward approach iterates through the array from left to right while tracking the first and last positions where the target appears. When you encounter the target for the first time, store the index as the starting position. Continue scanning and update the ending index whenever the value appears again. This approach works for any array but ignores the fact that the array is sorted, so it runs in O(n) time with constant O(1) extra space.
Approach 2: Modified Binary Search for First and Last Position (O(log n) time, O(1) space)
The optimal solution leverages binary search. Instead of stopping when the target is found, the search continues to locate the boundary positions. Run binary search twice: once to find the leftmost occurrence and once to find the rightmost occurrence. For the left boundary, when nums[mid] == target, move the search window to the left half to check if an earlier occurrence exists. For the right boundary, move the search window to the right half after a match.
This works because the array is sorted. Each binary search cuts the search space in half, resulting in O(log n) time. No additional data structures are required, so space complexity remains O(1). The two searches together still maintain logarithmic performance.
Implementation usually creates a helper function that returns a boundary index based on the direction of the search. Many solutions compute the left boundary first, then reuse the same logic with slightly different conditions to find the right boundary.
Recommended for interviews: Interviewers expect the modified binary search solution. A linear scan demonstrates basic correctness but fails to use the sorted property of the input. The two-pass boundary search shows you understand how to adapt binary search patterns, which is a common expectation in array and binary search interview problems.
| 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 |
| Modified Binary Search (Left and Right Boundaries) | O(log n) | O(1) | Best choice when the array is sorted and interviewers expect logarithmic search |