First and last occurrence
The problem
Given an array of integers nums sorted in non-decreasing order, find the starting and ending position of a given target value. If the target is not found in the array, return [-1, -1].
Input: nums = [5, 7, 7, 8, 8, 10], target = 8 Output: [3, 4] Explanation:The target is 8, and it appears in the array at indices 3 and 4, so the output is [3,4]
Input: nums = [5, 7, 7, 8, 8, 10], target = 6 Output: [-1, -1] Expalantion: The target is 6, which is not present in the array. Therefore, the output is [-1, -1].
Input: nums = [5, 7, 7, 8, 8, 10], target = 5
- 0 <= nums.length <= 105
- -109 <= nums[i] <= 109
- nums is a non-decreasing array.
- -109 <= target <= 109
cpp
class Solution{
public:
vector<int> searchRange(vector<int> &nums, int target) {
}
};java
class Solution {
public int[] searchRange(int[] nums, int target) {
}
}python
class Solution:
def searchRange(self, nums, target):javascript
class Solution {
searchRange(nums, target) {
}
}csharp
public class Solution {
public int[] SearchRange(int[] nums, int target) {
}
}go
func searchRange(nums []int, target int) []int {
}Stuck? Show a way to structure it+
- 01Run a lower-bound search for the first index with value at least target.
- 02Verify the candidate holds target.
- 03Run a right-biased search for the last index with value at most target.
- 04Return both positions or minus one values.
Reference answer
Then expect these follow-ups
How would you count occurrences from these indices?
Tests: follow-up reasoning
Can you express this using a reusable lower-bound helper?
Tests: follow-up reasoning
Free to read · better with Enzo
Practice this out loud with Enzo
Enzo runs it as a mock interview, pushes back with follow-ups, and grades you on the rubric.
Next question