Rotation Count
EasyIndex of the minimum = rotations
How many times it was rotated equals the position of the smallest number, found by halving.
The idea
A rotated sorted array's number of rotations equals the index of its minimum element, which binary search locates.
lo
hi
4
5
6
7
0
1
2
0
1
2
3
4
5
6
Step 1 of 5. Rotations = index of the minimum in [4,5,6,7,0,1,2]. Values: 4, 5, 6, 7, 0, 1, 2. Pointers: lo at index 0, hi at index 6.
1/5
Optimal
timeO(log n)spaceO(1)
Track the smallest's position.
1let lo = 0, hi = n - 1, idx = 0, best = Infinity;2while (lo <= hi) {3 const mid = (lo + hi) >> 1;4 if (a[lo] <= a[mid]) { if (a[lo] < best) { best = a[lo]; idx = lo; } lo = mid + 1; }5 else { if (a[mid] < best) { best = a[mid]; idx = mid; } hi = mid - 1; }6}7return idx;Input
- array
- [4, 5, 6, 7, 0, 1, 2]
Memory
- lo
- = 0 [4]
- hi
- = 6 [2]
- mid
- —
Output
- rotations
- —
Check yourself
3 quick questions about this walkthrough. A wrong answer costs nothing.
Examples
Example 1
- Input:
- nums = [4, 5, 6, 7, 0, 1, 2]
- Output:
- 4
- Explanation:
- The min sits at index 4 → rotated 4 times.
Example 2
- Input:
- nums = [3, 4, 5, 1, 2]
- Output:
- 3
- Explanation:
- Min at index 3.
Example 3
- Input:
- nums = [1, 2, 3]
- Output:
- 0
- Explanation:
- Already sorted → 0 rotations.
Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)
Finished the walkthrough? Add it to your streak.