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.
The goal is to use the binary search algorithm to achieve O(log n) time complexity. We perform two separate binary searches:
This solution uses two modified binary searches, one to find the first occurrence of the target and another to find the last occurrence. The code makes sure to continue searching even if the target is found to ensure the first or last position is located.
Time Complexity: O(log n) due to binary search. Space Complexity: O(1) as no extra space is used apart from input and output.
| 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 |
First and Last Position of Element in Sorted Array - Binary Search - Leetcode 34 • NeetCode • 115,942 views views
Watch 9 more video solutions →Practice Find First and Last Position of Element in Sorted Array with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor