Find First and Last Position of Element in Sorted Array
Asked at Meta, Atlassian, Oracle
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.
Asked At
| Company | Difficulty | |
|---|---|---|
| Meta | Medium | View all Meta questions → |
| Atlassian | Medium | View all Atlassian questions → |
| Oracle | Medium | View all Oracle 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.
Visual walkthrough for [5,7,7,8,8,10], target=8:
First position search: lo=0, hi=5. mid=2 (7<8), lo=3. mid=4 (8==8), result=4, hi=3. mid=3 (8==8), result=3, hi=2. lo>hi. First=3.
Last position search: lo=0, hi=5. mid=2 (7<8), lo=3. mid=4 (8==8), result=4, lo=5. mid=5 (10>8), hi=4. lo>hi. Last=4.
Result: [3, 4].
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).
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
def 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 is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
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. 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.