First and Last Occurrence
EasylowerBound(x) and upperBound(x) − 1
Use two halving searches to find where a repeated number first appears and where it last appears.
The idea
The first occurrence is the lower bound of x; the last is one before the upper bound. Two boundary searches pin the range.
5
7
7
8
8
10
0
1
2
3
4
5
target8
Step 1 of 8. Brute force: scan the whole array, noting the first and last 8. Values: 5, 7, 7, 8, 8, 10. target 8.
1/8
Brute force
timeO(n)spaceO(1)
Scan noting first & last.
1let first = -1, last = -1;2for (let i = 0; i < n; i++)3 if (nums[i] === target) { if (first < 0) first = i; last = i; }4return [first, last];Input
- array
- [5, 7, 7, 8, 8, 10]
Memory
- i
- —
- target
- 8
Output
- answer
- —
Check yourself
3 quick questions about this walkthrough. A wrong answer costs nothing.
Examples
Example 1
- Input:
- nums = [5, 7, 7, 8, 8, 10], target = 8
- Output:
- [3, 4]
- Explanation:
- 8 spans indices 3 to 4.
Example 2
- Input:
- nums = [5, 7, 7, 8, 8, 10], target = 6
- Output:
- [-1, -1]
- Explanation:
- 6 is missing → [-1,-1].
Example 3
- Input:
- nums = [1, 1, 1], target = 1
- Output:
- [0, 2]
- Explanation:
- All 1s: from index 0 to 2.
Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)
Finished the walkthrough? Add it to your streak.