34. Find First and Last Position of Element in Sorted Array
Asked at Meta, Atlassian, Oracle, Bloomberg and 1 more
Difficulty
Medium
Time
O(log n)
Space
O(1)
Pattern
Array
Companies
5
Problem
You are given an array nums sorted in non-decreasing order (each element is greater than or equal to the one before it), and a value target. Return the first and last index where target appears, as a two-element array [first, last].
If target does not appear in nums at all, return [-1, -1]. This also covers the case of an empty array.
Because the array is sorted, you must solve it in O(log n) time — a plain scan from left to right is too slow. The trick is to run binary search twice: once to find the leftmost copy of target, and once to find the rightmost copy.
Find the block of equal values
Constraints
- ●
0 <= nums.length <= 10^5 - ●
-10^9 <= nums[i] <= 10^9 - ●
nums is sorted in non-decreasing order - ●
-10^9 <= target <= 10^9
Examples
nums = [5,7,7,8,8,10], target = 8[3,4]nums = [5,7,7,8,8,10], target = 6[-1,-1]nums = [], target = 0[-1,-1]Asked At
5 companies| Company | Difficulty | |
|---|---|---|
| Meta | Medium | View all Meta questions → |
| Atlassian | Medium | View all Atlassian questions → |
| Oracle | Medium | View all Oracle questions → |
| Bloomberg | Medium | View all Bloomberg questions → |
| TikTok | Medium | View all TikTok questions → |
How to Think About It
Two binary searches: one to find the leftmost (first) occurrence, one to find the rightmost (last) occurrence. Each is O(log n).
Leftmost binary search: when you find target, don't stop. Continue searching left (hi = mid - 1) to find an earlier occurrence. The leftmost position is stored when target is first found.
Rightmost binary search: when you find target, continue searching right (lo = mid + 1) to find a later occurrence. The rightmost position is updated each time target is found.
Edge cases: target not found (return [-1,-1]), single element matching target (return [0,0]), all elements equal to target (return [0, n-1]).
Optimal Approach
Step 1: Find leftmost position using modified binary search:
- When nums[mid] >= target, move hi = mid - 1
- When nums[mid] < target, move lo = mid + 1
- After loop, check if lo is valid and nums[lo] == target
Step 2: Find rightmost position using modified binary search:
- When nums[mid] <= target, move lo = mid + 1
- When nums[mid] > target, move hi = mid - 1
- After loop, check if hi is valid and nums[hi] == target
Step 3: Return [leftmost, rightmost] or [-1, -1] if not found.
Time: O(log n) (two binary searches). Space: O(1).
Two binary searches
What Trips People Up in Real Interviews
Solving with linear scan O(n) instead of two binary search passes. The problem explicitly requires O(log n). A linear scan will pass tests but violate the constraint, and the interviewer will reject it.
Confusing the two binary search conditions. For the leftmost position, when nums[mid] >= target, set hi = mid - 1 to keep searching left. For the rightmost, when nums[mid] <= target, set lo = mid + 1 to keep searching right. Mixing these up returns wrong bounds.
Off-by-one errors when returning the result. The leftmost search stores the result in lo after the loop, not mid. The rightmost search stores it in hi. Returning mid or the wrong variable gives incorrect positions.
Not checking validity after the loop. lo might be out of bounds (lo >= len(nums)) or nums[lo] might not equal target (target not found). Always validate before returning, otherwise you return garbage values.
Using a single binary search to find any occurrence and then expanding outward with while loops. This degrades to O(n) in the worst case (all elements equal to target). Two independent binary search passes are required.
Solution Code
O(log n) timedef searchRange(nums, target):
def findLeft():
lo, hi = 0, len(nums) - 1
while lo <= hi:
mid = (lo + hi) // 2
if nums[mid] >= target:
hi = mid - 1
else:
lo = mid + 1
return lo if lo < len(nums) and nums[lo] == target else -1
def findRight():
lo, hi = 0, len(nums) - 1
while lo <= hi:
mid = (lo + hi) // 2
if nums[mid] <= target:
lo = mid + 1
else:
hi = mid - 1
return hi if hi >= 0 and nums[hi] == target else -1
left = findLeft()
if left == -1:
return [-1, -1]
return [left, findRight()]Frequently Asked Questions
What is the Find First and Last Position of Element in Sorted Array problem?
Given a sorted array of integers nums and a target value, return the starting and ending position of the target. If the target is not found, return [-1, -1]. You must write an algorithm with `O(log n)` runtime complexity.
How do you solve Find First and Last Position of Element in Sorted Array?
The optimal approach runs in O(log n) time and O(1) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.
What companies ask Find First and Last Position of Element in Sorted Array?
Find First and Last Position of Element in Sorted Array is asked at Meta, Atlassian, Oracle, Bloomberg, TikTok. It is a medium difficulty problem.
What are common mistakes on Find First and Last Position of Element in Sorted Array?
- Solving with linear scan `O(n)` instead of two `binary search` passes. The problem explicitly requires `O(log n)`. A linear scan will pass tests but violate the constraint, and the interviewer will reject it.
- Confusing the two `binary search` conditions. For the leftmost position, when `nums[mid] >= target`, set `hi = mid - 1` to keep searching left. For the rightmost, when `nums[mid] <= target`, set `lo = mid + 1` to keep searching right. Mixing these up returns wrong bounds.
- Off-by-one errors when returning the result. The leftmost search stores the result in `lo` after the loop, not `mid`. The rightmost search stores it in `hi`. Returning `mid` or the wrong variable gives incorrect positions.
- Not checking validity after the loop. `lo` might be out of bounds (`lo >= len(nums)`) or `nums[lo]` might not equal `target` (target not found). Always validate before returning, otherwise you return garbage values.
- Using a single `binary search` to find any occurrence and then expanding outward with `while` loops. This degrades to `O(n)` in the worst case (all elements equal to target). Two independent `binary search` passes are required.