61. Find First and Last Position of Element in Sorted Array
🔗 LeetCode Problem: 34. Find First and Last Position of Element in Sorted Array
📊 Difficulty: Medium
🏷️ Topics: Array, Binary Search
Problem Statement
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 <= 10^5
- -10^9 <= nums[i] <= 10^9
- nums is a non-decreasing array
- -10^9 <= target <= 10^9
🎨 Visual Understanding
The Problem Visualized
nums = [5, 7, 7, 8, 8, 10], target = 8
Array: [5, 7, 7, 8, 8, 10]
Index: 0 1 2 3 4 5
↑ ↑
first last
First occurrence of 8: index 3
Last occurrence of 8: index 4
Answer: [3, 4]
nums = [5, 7, 7, 8, 8, 10], target = 6
Array: [5, 7, 7, 8, 8, 10]
Index: 0 1 2 3 4 5
↑ ↑
7 < 6? NO
8 > 6? YES
6 is not in array
Answer: [-1, -1]
nums = [1, 2, 2, 2, 2, 2, 3, 4, 5], target = 2
Array: [1, 2, 2, 2, 2, 2, 3, 4, 5]
Index: 0 1 2 3 4 5 6 7 8
↑ ↑
first last
Multiple occurrences of 2
First: index 1
Last: index 5
Answer: [1, 5]
🚨 CRITICAL INSIGHT - Why Two Binary Searches Work
The Key Pattern!
This problem requires finding TWO positions:
1. FIRST (leftmost) occurrence
2. LAST (rightmost) occurrence
Key Insight:
These are TWO separate binary searches!
- Find first: "Find leftmost position where nums[i] == target"
- Find last: "Find rightmost position where nums[i] == target"
Pattern Recognition:
[5, 7, 7, 8, 8, 8, 8, 10]
↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓
< < < = = = = >
↑ ↑
first last
We're finding the BOUNDARIES of target's range!
Before first: all elements < target
After last: all elements > target
Between first-last: all elements = target
Find First Occurrence Pattern
We want the LEFTMOST position where nums[i] == target
Modified binary search:
When nums[mid] == target:
DON'T return immediately!
This might not be the first occurrence
There might be more to the left
So: result = mid (track it)
right = mid - 1 (search left)
When nums[mid] < target:
First occurrence is to the right
left = mid + 1
When nums[mid] > target:
First occurrence is to the left (or doesn't exist)
right = mid - 1
Example: [5, 7, 7, 8, 8, 8, 10], target = 8
Check mid=3, nums[3]=8 (found!)
But is it the first? Check left!
result = 3, right = 2
Check mid=1, nums[1]=7 < 8
First is to the right
left = 2
Check mid=2, nums[2]=7 < 8
First is to the right
left = 3
Now left > right, loop ends
result = 3 (first occurrence!) ✓
Find Last Occurrence Pattern
We want the RIGHTMOST position where nums[i] == target
Modified binary search:
When nums[mid] == target:
DON'T return immediately!
This might not be the last occurrence
There might be more to the right
So: result = mid (track it)
left = mid + 1 (search right)
When nums[mid] < target:
Last occurrence is to the right
left = mid + 1
When nums[mid] > target:
Last occurrence is to the left (or doesn't exist)
right = mid - 1
Example: [5, 7, 7, 8, 8, 8, 10], target = 8
Check mid=3, nums[3]=8 (found!)
But is it the last? Check right!
result = 3, left = 4
Check mid=5, nums[5]=8 (found!)
result = 5, left = 6
Check mid=6, nums[6]=10 > 8
Last is to the left
right = 5
Now left > right, loop ends
result = 5 (last occurrence!) ✓
🎯 Approach 1: Linear Search (Brute Force)
The Most Natural Thinking 💭
Core Logic:
Scan array left to right:
Find first occurrence of target
Continue to find last occurrence
Return range
Implementation
public int[] searchRange(int[] nums, int target) {
int first = -1, last = -1;
// Find first and last
for (int i = 0; i < nums.length; i++) {
if (nums[i] == target) {
if (first == -1) {
first = i; // First occurrence
}
last = i; // Keep updating last
}
}
return new int[]{first, last};
}
⏰ Time: O(n) - Scan entire array
💾 Space: O(1) - Only variables
❌ Problem: Doesn't meet O(log n) requirement!
🎯 Approach 2: Two Binary Searches (Optimal) ⭐
Better Approach 💡
🧠 The Core Insight
Use TWO separate binary searches:
1. Binary search for FIRST occurrence
2. Binary search for LAST occurrence
Key difference from classic BS:
When we find target, DON'T return immediately!
Keep searching for boundaries!
The Strategy:
findFirst():
When found: result = mid, right = mid - 1 (search left)
findLast():
When found: result = mid, left = mid + 1 (search right)
Both: O(log n)
Total: O(log n) + O(log n) = O(log n) ✓
Implementation
public int[] searchRange(int[] nums, int target) {
int first = findFirst(nums, target);
int last = findLast(nums, target);
return new int[]{first, last};
}
private int findFirst(int[] nums, int target) {
int left = 0, right = nums.length - 1;
int result = -1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
result = mid; // Found, but keep searching left
right = mid - 1; // Look for earlier occurrence
} else if (nums[mid] < target) {
left = mid + 1; // Target is to the right
} else {
right = mid - 1; // Target is to the left
}
}
return result;
}
private int findLast(int[] nums, int target) {
int left = 0, right = nums.length - 1;
int result = -1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
result = mid; // Found, but keep searching right
left = mid + 1; // Look for later occurrence
} else if (nums[mid] < target) {
left = mid + 1; // Target is to the right
} else {
right = mid - 1; // Target is to the left
}
}
return result;
}
⏰ Time: O(log n) - Two binary searches
💾 Space: O(1) - Only variables
🔍 Dry Run
Example 1: nums = [5, 7, 7, 8, 8, 10], target = 8
Finding FIRST occurrence:
════════════════════════════════════════════════════════
Initial: left = 0, right = 5, result = -1
[5, 7, 7, 8, 8, 10]
↑ ↑
left right
Iteration 1:
mid = 2
nums[2] = 7 < 8
Search right
left = 3
[5, 7, 7, 8, 8, 10]
↑ ↑
left right
Iteration 2:
mid = 4
nums[4] = 8 == 8 ✓
Found! But check if there's earlier
result = 4
right = 3 (search left)
[5, 7, 7, 8, 8, 10]
↑ ↑
right left (wait, this is backwards)
Let me recalculate:
left = 3, right = 5, mid = 4
[5, 7, 7, 8, 8, 10]
↑ ↑
left right
Iteration 2:
mid = 3 + (5 - 3) / 2 = 4
nums[4] = 8 == 8 ✓
result = 4
right = 3
[5, 7, 7, 8, 8, 10]
↑ ↑
right left
Iteration 3:
mid = 3 + (3 - 3) / 2 = 3
nums[3] = 8 == 8 ✓
result = 3 (earlier!)
right = 2
[5, 7, 7, 8, 8, 10]
↑ ↑
right left
Loop ends (left > right)
First = 3 ✓
Finding LAST occurrence:
════════════════════════════════════════════════════════
Initial: left = 0, right = 5, result = -1
Iteration 1:
mid = 2, nums[2] = 7 < 8
left = 3
Iteration 2:
mid = 4, nums[4] = 8 == 8 ✓
result = 4
left = 5 (search right)
Iteration 3:
mid = 5, nums[5] = 10 > 8
right = 4
Loop ends (left > right)
Last = 4 ✓
Answer: [3, 4] ✓
Example 2: nums = [5, 7, 7, 8, 8, 10], target = 6
Finding FIRST:
════════════════════════════════════════════════════════
Iteration 1:
mid = 2, nums[2] = 7 > 6
right = 1
Iteration 2:
mid = 0, nums[0] = 5 < 6
left = 1
Iteration 3:
mid = 1, nums[1] = 7 > 6
right = 0
Loop ends (left > right)
First = -1 (not found)
Finding LAST:
════════════════════════════════════════════════════════
(Same process, also returns -1)
Answer: [-1, -1] ✓
Example 3: nums = [1], target = 1
Finding FIRST:
mid = 0, nums[0] = 1 == 1
result = 0
right = -1
Loop ends
First = 0
Finding LAST:
mid = 0, nums[0] = 1 == 1
result = 0
left = 1
Loop ends
Last = 0
Answer: [0, 0] ✓
🎯 Why This Works - Deep Dive
The "Find First" Logic:
═══════════════════════════════════════════════════════════════
Goal: Find LEFTMOST position where nums[i] == target
When nums[mid] == target:
This is A valid position
But maybe not the FIRST
Strategy:
1. Save it: result = mid
2. Keep searching LEFT: right = mid - 1
3. If we find earlier, update result
4. If no earlier, result stays
Visual: [5, 7, 7, 8, 8, 8, 10], target = 8
Found at mid=5 (value 8)
result = 5, search left [5,7,7,8,8]
Found at mid=3 (value 8)
result = 3, search left [5,7,7]
No more 8s to the left
result = 3 is the first! ✓
The "Find Last" Logic:
═══════════════════════════════════════════════════════════════
Goal: Find RIGHTMOST position where nums[i] == target
When nums[mid] == target:
This is A valid position
But maybe not the LAST
Strategy:
1. Save it: result = mid
2. Keep searching RIGHT: left = mid + 1
3. If we find later, update result
4. If no later, result stays
Visual: [5, 7, 7, 8, 8, 8, 10], target = 8
Found at mid=3 (value 8)
result = 3, search right [8,8,10]
Found at mid=4 (value 8)
result = 4, search right [8,10]
Found at mid=5? No, it's 10
result = 4 is the last! ✓
Why Track result Separately?
═══════════════════════════════════════════════════════════════
We need to preserve the last valid position found:
Without result:
Find 8, search left
Find 8 again, search left
Loop ends
Lost the position! ✗
With result:
Find 8, result = 4, search left
Find 8, result = 3, search left
Loop ends
result = 3 preserved! ✓
Time Complexity:
═══════════════════════════════════════════════════════════════
findFirst(): O(log n)
findLast(): O(log n)
Total: O(log n) + O(log n) = O(log n) ✓
Even though two searches, still logarithmic!
Alternative: Single Pass with Early Optimization
// Optimization: Check if target exists first
public int[] searchRange(int[] nums, int target) {
int first = findFirst(nums, target);
// If first not found, last won't be found either
if (first == -1) {
return new int[]{-1, -1};
}
// Only search for last if first exists
int last = findLast(nums, target);
return new int[]{first, last};
}
⚠️ Common Mistakes to Avoid
Mistake 1: Returning immediately when found
// ❌ WRONG - Returns first match, not first occurrence
if (nums[mid] == target) {
return mid; // Might not be leftmost/rightmost!
}
// ✓ CORRECT - Keep searching for boundary
if (nums[mid] == target) {
result = mid;
right = mid - 1; // For first
// OR
left = mid + 1; // For last
}
Mistake 2: Not tracking result
// ❌ WRONG - Loses the position
if (nums[mid] == target) {
right = mid - 1; // No tracking!
}
// ✓ CORRECT - Track it
if (nums[mid] == target) {
result = mid; // Save it!
right = mid - 1;
}
Mistake 3: Wrong search direction
// ❌ WRONG - findFirst but searching right
if (nums[mid] == target) {
result = mid;
left = mid + 1; // Wrong direction for first!
}
// ✓ CORRECT - Search left for first
if (nums[mid] == target) {
result = mid;
right = mid - 1; // Correct for first
}
Mistake 4: Using same function for both
// ❌ WRONG - Can't find both with single function
int pos = binarySearch(nums, target);
return new int[]{pos, pos}; // Wrong if duplicates!
// ✓ CORRECT - Two separate searches
int first = findFirst(nums, target);
int last = findLast(nums, target);
Mistake 5: Not handling not found case
// ❌ WRONG - Doesn't handle target not found
int first = findFirst(nums, target);
int last = findLast(nums, target);
// What if both are -1?
// ✓ CORRECT - Initialize result to -1
int result = -1; // Default not found
🎯 Pattern Recognition
Problem Type: Binary Search - Find Boundaries/Range
Core Pattern: Find First and Last Occurrence
When to Apply:
✓ Sorted array with DUPLICATES
✓ Need to find RANGE of target
✓ Find FIRST and LAST position
✓ Need O(log n) time
✓ Find boundaries of element
Recognition Keywords:
- "First and last position"
- "Starting and ending position"
- "Range"
- "Sorted array"
- "Non-decreasing"
- O(log n) runtime
Similar Problems:
- First Bad Version (LC 278) - Find first only
- Search Insert Position (LC 35) - Find position
- Count of Range Sum (LC 327) - Uses boundaries
- Find K Closest Elements (LC 658)
Key Difference from Classic BS:
┌────────────────────────────────────────────┐
│ Classic Binary Search: │
│ - Return immediately when found │
│ - Single search │
│ │
│ Find Range (This Problem): │
│ - DON'T return when found │
│ - Keep searching for boundaries │
│ - TWO separate searches │
│ - Track result variable │
└────────────────────────────────────────────┘
The "keep searching" is the KEY difference!
🧠 Interview Strategy
Step 1: "Need first AND last position → Two binary searches"
Step 2: "Find first: search left when found"
Step 3: "Find last: search right when found"
Step 4: "Track result in both searches"
Step 5: "Return [-1, -1] if not found"
Key Points to Mention:
- TWO separate binary searches
- Don't return immediately when found
- Track best result in each search
- Find first: right = mid - 1 when found
- Find last: left = mid + 1 when found
- Both searches independent
- Time: O(log n), Space: O(1)
- Can optimize: check first before finding last
Why This Approach?
"I need to find both the first and last positions of the target.
Since the array is sorted, I'll use binary search for O(log n)
time. The key insight is that I need TWO separate binary searches.
For finding the first occurrence, when I find the target, I don't
return immediately. Instead, I save it as a potential answer and
continue searching left to see if there's an earlier occurrence.
Similarly for the last, I search right. Each search is O(log n),
so total time is still O(log n)."
Code Organization:
"I'll create two helper functions: findFirst and findLast. They're
almost identical, with the key difference being the search direction
when target is found. This makes the code clean and maintainable."
📝 Quick Revision Notes
🎯 Core Concept:
Find Range of Target: Use TWO binary searches - one for first, one for last. Key: DON'T return when found, keep searching! First: search left (right = mid - 1). Last: search right (left = mid + 1). Track result variable!
⚡ Quick Implementation:
import java.util.Arrays;
class Test {
public int[] searchRange(int[] a, int k) {
// Range means always find left and right indices.
int leftIndex = getLeftIndex(a, k);
int rightIndex = getRightIndex(a, k);
return new int[] {leftIndex, rightIndex};
}
private int getRightIndex(int[] a, int k) {
int index = -1;
int left = 0;
int right = a.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if(a[mid] == k) {
// return mid; // do not decide early
index = mid; // track the current result and try for the best
left = mid + 1; // check if k is present somewhere else on the right side still for better res
} else if(a[mid] < k) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return index;
}
private int getLeftIndex(int[] a, int k) {
int index = -1;
int left = 0;
int right = a.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if(a[mid] == k) {
// return mid; // do not decide early
index = mid; // track the current result and try for the best
right = mid - 1; // check if k is present somewhere else on the left side still for better res
} else if(a[mid] < k) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return index;
}
public static void main(String[] args) {
Test t = new Test();
System.out.println(Arrays.toString(t.searchRange(new int[] {5,7,7,8,8,10}, 8))); // [3, 4]
System.out.println(Arrays.toString(t.searchRange(new int[] {5,7,7,8,8,10}, 6))); // [-1, -1]
System.out.println(Arrays.toString(t.searchRange(new int[] {}, 0))); // [-1, -1]
System.out.println(Arrays.toString(t.searchRange(new int[] {5}, 5))); // [0, 0]
System.out.println(Arrays.toString(t.searchRange(new int[] {5}, 3))); // [-1, -1]
System.out.println(Arrays.toString(t.searchRange(new int[] {2, 2, 2, 2, 2}, 2))); // [0, 4]
System.out.println(Arrays.toString(t.searchRange(new int[] {1, 2, 3, 4, 5}, 1))); // [0, 0]
System.out.println(Arrays.toString(t.searchRange(new int[] {1, 2, 3, 4, 5}, 5))); // [4, 4]
System.out.println(Arrays.toString(t.searchRange(new int[] {1, 2, 3, 4, 5}, 3))); // [2, 2]
}
}
🔑 Key Insights:
- Pattern: Find First + Find Last (Two Binary Searches)
- Key Difference: DON'T return when found
- Find First: When found,
right = mid - 1(search left) - Find Last: When found,
left = mid + 1(search right) - Track Result: Must save each valid position found
- Initialize:
result = -1(default not found) - Independent: Two separate searches
- Time: O(log n) + O(log n) = O(log n)
- Space: O(1)
🎪 Memory Aid:
"Found it? Don't stop! Track it, keep searching the boundary!"
Think: "First → Left, Last → Right, Track result!"
💡 The Key Insight:
When target found:
findFirst:
result = mid (save it)
right = mid - 1 (search LEFT for earlier)
findLast:
result = mid (save it)
left = mid + 1 (search RIGHT for later)
Both: Keep the last valid position found!
⚠️ Critical Details:
1. TWO searches: findFirst + findLast
2. Track: int result = -1 (in each)
3. When found: DON'T return immediately
4. First: right = mid - 1 (go left)
5. Last: left = mid + 1 (go right)
6. Return: result (not mid)
🔥 The Pattern:
[5, 7, 7, 8, 8, 8, 10], target = 8
↓ ↓ ↓ ↓
< = = >
↑ ↑
first last
Finding boundaries of equal elements!
First: Keep going left when ==
Last: Keep going right when ==
💡 Why Track Result:
Without tracking:
Find 8 at index 5
Search left
Find 8 at index 3
Search left
No more 8s
Loop ends
Lost position 3! ✗
With tracking:
Find 8, result = 5
Find 8, result = 3
Loop ends
result = 3 preserved! ✓
🧪 Edge Cases
Case 1: Empty array
Input: nums = [], target = 0
Output: [-1, -1]
Case 2: Single element - found
Input: nums = [5], target = 5
Output: [0, 0]
Case 3: Single element - not found
Input: nums = [5], target = 3
Output: [-1, -1]
Case 4: All elements same
Input: nums = [2, 2, 2, 2, 2], target = 2
Output: [0, 4]
Case 5: Target at boundaries
Input: nums = [1, 2, 3, 4, 5], target = 1
Output: [0, 0]
Input: nums = [1, 2, 3, 4, 5], target = 5
Output: [4, 4]
Case 6: No duplicates
Input: nums = [1, 2, 3, 4, 5], target = 3
Output: [2, 2]
Case 7: Target not present
Input: nums = [1, 3, 5, 7, 9], target = 4
Output: [-1, -1]
All handled correctly! ✓
Related Patterns
- First Bad Version (LC 278) - Find first occurrence pattern
- Search Insert Position (LC 35) - Find position to insert
- Find K Closest Elements (LC 658) - Uses boundary finding
- Search for a Range (LC 34) - This problem!
Happy practicing! 🎯
Note: This is THE classic "find boundaries" pattern! Master the "don't return when found" technique - it appears in many variations!