The smallest value after a rotation
MediumStuck?
Show a hintHide the hint
Compare the middle with the rightmost value. Bigger means the drop is to the right, smaller means the answer is at or before the middle.
The idea behind this problem
Next in this lesson
The slowest speed that still finishes in timeA sorted list of distinct numbers has been rotated: some number of values were taken from the front and moved to the back. Find the smallest value.
For example [0, 1, 2, 4, 5, 6, 7] rotated three times becomes [4, 5, 6, 7, 0, 1, 2].
Worked example#
For [4, 5, 6, 7, 0, 1, 2], compare the middle with the rightmost value. That comparison tells you which half the rotation point is in:
| low | high | middle | nums[middle] | nums[high] | reasoning |
|---|---|---|---|---|---|
| 0 | 6 | 3 | 7 | 2 | 7 is bigger than 2, so the drop is to the right of the middle |
| 4 | 6 | 5 | 1 | 2 | 1 is smaller than 2, so this part is in order and the answer is at or left of the middle |
| 4 | 5 | 4 | 0 | 1 | in order again, move left |
| 4 | 4 | low meets high, and that is the answer: 0 |
Why compare against the right, not the left#
The list is in two sorted runs, and the smallest value is where the second begins. If the middle is bigger than the rightmost value, the middle is still in the first run, so the drop must be after it. If the middle is smaller, the middle is already in the second run, so the drop is at the middle or before it.
Comparing against the leftmost value does not work as cleanly, because a list that was not rotated at all has no drop and the comparison misleads you. Comparing against the right handles that case without a special branch: an unrotated list simply keeps moving left until it lands on position 0.
Constraints#
1 <= n <= 100000- All values distinct
- The list is a rotation of a sorted list, possibly rotated zero times
Input
nums is a count then that many integers.
Output
The smallest value.
Examples
Input
5 3 4 5 1 2
Output
1
The drop from 5 to 1 is where the original start went.
Input
7 4 5 6 7 0 1 2
Output
0
Rotated three times, so 0 is the smallest.
Input
4 11 13 15 17
Output
11
Not rotated at all, so the first value is the smallest.
Something wrong with this problem? Report an issue
Ready to try it
Write your solution in C, C++, Java or Python and see every test case come back with the time and memory it took.
Free, and it stays free. No card.