381. Turned Shelf with Repeats
A bakery lines up trays of loaves labelled by size, from the smallest size to the largest, and several trays can share the same size. During the night the line was rotated, so it now begins at some tray in the middle of the original order, for example [3, 3, 4, 1, 2, 2, 3].
Given the rotated array nums (the values are in non-decreasing order before the rotation) and an integer target, return true if a tray of size target is in the line and false otherwise. Because sizes can repeat, the worst case cannot beat a linear scan, but your solution should use binary search and be fast whenever the sizes are mostly different.
Example 1
- Input:
- nums = [3,3,4,1,2,2,3], target = 4
- Output:
- true
- Explanation:
A tray of size 4 is in the line.
Example 2
- Input:
- nums = [3,3,4,1,2,2,3], target = 5
- Output:
- false
- Explanation:
No tray has size 5, so the answer is false.
Constraints
1 ≤ nums.length ≤ 106
-109 ≤ nums[i], target ≤ 109nums is a non-decreasing array rotated by an unknown number of positions (possibly zero). Values may repeat.
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) on average, O(n) in the worst case
- Space
- O(1)