379. First and Last Seen
A weather station records one temperature reading per hour, and the readings in nums have been sorted from lowest to highest, with repeated values allowed. An analyst asks when a particular reading, target, first and last shows up in the sorted list.
Return an array [first, last] holding the first and the last index at which target appears in nums. If target does not appear, return [-1, -1]. The list can hold hundreds of thousands of readings, so your solution must run in O(log n) time. A scan through the whole array is too slow.
Example 1
- Input:
- nums = [2,4,4,4,9,12], target = 4
- Output:
- [1,3]
- Explanation:
The value 4 first appears at index 1 and last appears at index 3.
Example 2
- Input:
- nums = [1,2,3], target = 7
- Output:
- [-1,-1]
- Explanation:
7 is not in the array, so the answer is [-1, -1].
Constraints
0 ≤ nums.length ≤ 106
-109 ≤ nums[i], target ≤ 109nums is sorted in non-decreasing order.
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 1,200 msC++ 300 msJava 600 msJavaScript 600 msTypeScript 600 ms
Expected complexity
- Time
- O(log n)
- Space
- O(1)