353. Lowest With Repeats
A bakery sorts its trays by loaf size from smallest to largest, and several trays may share a size. Overnight the line was rotated, so it now begins somewhere in the middle, for example [4, 4, 5, 1, 2, 2, 4].
Given the rotated array nums, return the smallest tray size in it. Because sizes can repeat, there are inputs where nothing beats looking at almost every tray, but your solution should use binary search so that it is fast whenever the sizes are mostly different, and it must never be slower than O(n).
Example 1
- Input:
- nums = [4,4,5,1,2,2,4]
- Output:
- 1
- Explanation:
The smallest tray size is 1.
Example 2
- Input:
- nums = [6,6,6]
- Output:
- 6
- Explanation:
Every tray has size 6, so the smallest is 6.
Constraints
1 ≤ nums.length ≤ 106
-109 ≤ nums[i] ≤ 109nums is a non-decreasing array rotated by an unknown amount (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)