Count the Rotations
Problem
A list of distinct numbers was sorted in increasing order and then rotated to the right r times, where one rotation moves the last element to the front and r is smaller than the list length. Given the rotated list, return r. The list has at least one element, and the answer should take O(log n) time.
Examples
Input: nums = [15, 18, 2, 3, 6, 12]
Output: 2
Why: the smallest value, 2, was carried two places to the rightInput: nums = [1, 2, 3, 4]
Output: 0
Why: the list was never rotatedInput: nums = [9]
Output: 0
Why: edge case, one element cannot moveHints
0 / 3
Each rotation pushes the smallest value one step to the right, so r is simply where the smallest value now sits.
A linear scan finds the minimum, but compare the middle element with the last one: that single comparison tells you which side of the middle the drop is on.
Keep a window from lo to hi. If the middle value is greater than the value at hi, the drop, and so the minimum, lies strictly right of the middle. Otherwise the stretch from the middle to hi is sorted and the minimum is at the middle or to its left. Shrink until lo meets hi.
Solution
After rotation the list is two increasing runs, and the first element of the second run is the minimum, whose index equals the number of rotations. Comparing the middle with the right end of the window reveals which run the middle belongs to: a larger middle belongs to the first run, so the minimum is to its right. A smaller middle belongs to the second run, so the minimum is at the middle or before it, which is why hi moves to mid and not past it. Time is O(log n), and space is O(1).
def rotations(nums):
lo, hi = 0, len(nums) - 1
while lo < hi:
mid = (lo + hi) // 2
if nums[mid] > nums[hi]:
lo = mid + 1 # the drop lies right of mid
else:
hi = mid # mid..hi is sorted, the minimum is at mid or left
return lo # index of the minimum = rotations
print(rotations([15, 18, 2, 3, 6, 12])) # -> 2
print(rotations([1, 2, 3, 4])) # -> 0
print(rotations([9])) # -> 0Stuck on the idea rather than the code? Search in Rotated Array covers it.