Find out how many times the array is rotated
EasyThe index of the minimum is the rotation count
Problem
Given an integer array nums of size n, sorted in ascending order with distinct values. The array has been right rotated an unknown number of times, between 0 and n-1 (including). Determine the number of rotations performed on the array.
The number of rotations equals the index of the smallest element — find it with binary search.
The idea
Rotating a sorted array k times moves the original first element to index k, which is exactly where the minimum now sits. So finding the minimum's index with the rotated-array binary search answers the question directly.
The trick
- Rotation count = index of the smallest element.
- An already-sorted array gives index 0 — zero rotations.
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.
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.
Constraints
- n == nums.length
- 1 <= n <= 10^4
- -10^4 <= nums[i] <= 10^4
- All the integers of nums are unique.
Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)
Finished the walkthrough? Add it to your streak.