Skip to main content
CodePeetCodePeet
CodePeet 444 Complete DSA Sheet

Rotation Count in a Rotated Sorted array

EASYProblemSolveExternal Links

Description

Given an increasing sorted rotated array arr[] of distinct integers, the array has been right-rotated k times. Find the value of k — the number of times the array was rotated.

A right rotation means the last element is moved to the first position, and all remaining elements shift one position to the right.

For example, if we have arr[] = [2, 4, 6, 9]:

  • After 1st rotation: [9, 2, 4, 6]
  • After 2nd rotation: [6, 9, 2, 4]

So if we are given [6, 9, 2, 4], the answer is 2.

The key insight is that the rotation count equals the index of the minimum element in the rotated array.

Examples

Example 1

Input: arr = [15, 18, 2, 3, 6, 12]

Output: 2

Explanation:
The original sorted array is [2, 3, 6, 12, 15, 18].
After 2 right rotations → [15, 18, 2, 3, 6, 12].
The minimum element 2 is at index 2, so k = 2.

Example 2

Input: arr = [5, 1, 2, 3, 4]

Output: 1

Explanation:
The original sorted array is [1, 2, 3, 4, 5].
After 1 right rotation → [5, 1, 2, 3, 4].
The minimum element 1 is at index 1, so k = 1.

Example 3

Input: arr = [7, 9, 11, 12, 5]

Output: 4

Explanation:
The original sorted array is [5, 7, 9, 11, 12].
After 4 right rotations → [7, 9, 11, 12, 5].
The minimum element 5 is at index 4, so k = 4.

Example 4

Input: arr = [1, 2, 3, 4, 5]

Output: 0

Explanation:
The array is already sorted (no rotation). The minimum element 1 is at index 0, so k = 0.

Constraints

  • 1 ≤ arr.size() ≤ 10⁵
  • 1 ≤ arr[i] ≤ 10⁷
  • All elements are distinct

Editorial

Brute Force - Linear Scan

Intuition

The rotation count equals the index of the minimum element. Why? Because in a sorted array, the minimum element is at index 0. Each right rotation shifts everything right by one position, so after k rotations, the minimum element has moved from index 0 to index k.

So the simplest approach is: scan through the entire array, find the minimum element, and return its index.

Think of it like a clock that has been turned. If you know where the "12" (the smallest number) ended up, you know how far the clock was turned. We just look at every position on the clock until we find the "12".

Alternatively, we can find the rotation point by looking for where the sorted order breaks — the point where arr[i] < arr[i-1]. That index i is where the minimum sits and equals the rotation count.

Step-by-Step Explanation

Let's trace through with arr = [15, 18, 2, 3, 6, 12]:

Step 1: Initialize: min_val = arr[0] = 15, min_index = 0.

Step 2: Check arr[1] = 18. 18 > 15, not smaller. min_val = 15, min_index = 0.

Step 3: Check arr[2] = 2. 2 < 15, found a new minimum! min_val = 2, min_index = 2.

Step 4: Check arr[3] = 3. 3 > 2, not smaller. min_val = 2, min_index = 2.

Step 5: Check arr[4] = 6. 6 > 2, not smaller. min_val = 2, min_index = 2.

Step 6: Check arr[5] = 12. 12 > 2, not smaller. min_val = 2, min_index = 2.

Step 7: Finished scanning. The minimum element is 2 at index 2. Return 2. The array was rotated 2 times.

Linear Scan — Finding the Minimum Element — Watch as we scan through the rotated sorted array to find the minimum element. Its index equals the rotation count.

Algorithm

  1. Initialize min_val = arr[0] and min_index = 0
  2. Iterate through the array from index 1 to n-1:
    • If arr[i] < min_val, update min_val = arr[i] and min_index = i
  3. Return min_index — this is the rotation count

Code

class Solution {
public:
    int findKRotation(vector<int>& arr) {
        int minVal = arr[0];
        int minIndex = 0;
        
        for (int i = 1; i < arr.size(); i++) {
            if (arr[i] < minVal) {
                minVal = arr[i];
                minIndex = i;
            }
        }
        
        return minIndex;
    }
};
class Solution:
    def findKRotation(self, arr: list[int]) -> int:
        min_val = arr[0]
        min_index = 0
        
        for i in range(1, len(arr)):
            if arr[i] < min_val:
                min_val = arr[i]
                min_index = i
        
        return min_index
class Solution {
    public int findKRotation(int[] arr) {
        int minVal = arr[0];
        int minIndex = 0;
        
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] < minVal) {
                minVal = arr[i];
                minIndex = i;
            }
        }
        
        return minIndex;
    }
}

Complexity Analysis

Time Complexity: O(n)

We scan the entire array once to find the minimum element. Each element is visited exactly once, so the time is linear in the size of the array.

Space Complexity: O(1)

We only use two variables (min_val and min_index). No extra data structures are needed.

Why This Approach Is Not Efficient

The brute force scans every element to find the minimum, taking O(n) time. But we're throwing away a critical piece of information: the array is sorted (with a rotation).

In a normal unsorted array, O(n) is the best we can do to find the minimum. But a rotated sorted array has a special structure — it consists of two sorted halves. At any point, we can determine which half contains the minimum by comparing the middle element with the boundaries.

This is exactly the kind of structure that binary search exploits. Instead of checking every element, we can eliminate half the search space at each step, reducing the time from O(n) to O(log n).

For n = 10⁵ elements, this is the difference between 100,000 operations (linear) and about 17 operations (binary search).

Optimal Approach - Binary Search

Intuition

A rotated sorted array has a beautiful property: it consists of two sorted subarrays joined at the rotation point (the minimum element). For example, [15, 18, | 2, 3, 6, 12] — the left part [15, 18] is sorted and the right part [2, 3, 6, 12] is sorted.

We can use binary search to find the minimum element's index efficiently:

Key decision at each step: Compare arr[mid] with arr[high]:

  • If arr[mid] > arr[high]: The minimum must be in the right half (mid+1 to high). Why? Because arr[mid] is larger than arr[high], meaning the sorted order is broken between mid and high — that's where the rotation point lies.
  • If arr[mid] <= arr[high]: The minimum is in the left half (low to mid). Why? The right portion from mid to high is properly sorted, so the break point (minimum) must be at or before mid.

We also have an early exit: if arr[low] <= arr[high], the entire current range is already sorted, so arr[low] is the minimum and its index low is the answer.

Think of it like searching for a "break" in a string of beads arranged in increasing size around a circle. At each step, you check the middle bead — if it's larger than the rightmost bead in your current range, the break is to the right; otherwise, it's to the left.

Step-by-Step Explanation

Let's trace through with arr = [15, 18, 2, 3, 6, 12]:

Step 1: Initialize low = 0, high = 5.
Check: arr[low] = 15 ≤ arr[high] = 12? No (15 > 12). The range is NOT fully sorted, so the rotation point is within this range.

Step 2: Calculate mid = (0 + 5) / 2 = 2. arr[mid] = arr[2] = 2.
Compare arr[mid] = 2 with arr[high] = 12. Is 2 > 12? No.
So the minimum is at or before mid. Set high = mid = 2.

Step 3: Now low = 0, high = 2.
Check: arr[low] = 15 ≤ arr[high] = 2? No (15 > 2). Still not sorted.

Step 4: Calculate mid = (0 + 2) / 2 = 1. arr[mid] = arr[1] = 18.
Compare arr[mid] = 18 with arr[high] = 2. Is 18 > 2? Yes.
So the minimum is in the right half. Set low = mid + 1 = 2.

Step 5: Now low = 2, high = 2. low == high, loop ends.
Return low = 2. The array was rotated 2 times.

Binary Search — Finding the Rotation Point in O(log n) — Watch how binary search narrows down the search space by half at each step, quickly zeroing in on the minimum element (rotation point) without scanning the full array.

Algorithm

  1. Initialize low = 0, high = n - 1
  2. While low <= high:
    a. Early exit: If arr[low] <= arr[high], the current range is fully sorted → return low
    b. Calculate mid = (low + high) / 2
    c. If arr[mid] > arr[high]: The minimum is in the right half → set low = mid + 1
    d. Else: The minimum is at mid or in the left half → set high = mid
  3. Return low — the index of the minimum element, which is the rotation count

Code

class Solution {
public:
    int findKRotation(vector<int>& arr) {
        int low = 0, high = arr.size() - 1;
        
        while (low <= high) {
            // If current range is already sorted,
            // smallest is at low
            if (arr[low] <= arr[high])
                return low;
            
            int mid = (low + high) / 2;
            
            // If mid element > high element,
            // minimum is in the right half
            if (arr[mid] > arr[high])
                low = mid + 1;
            // Otherwise minimum is at mid or in left half
            else
                high = mid;
        }
        
        return low;
    }
};
class Solution:
    def findKRotation(self, arr: list[int]) -> int:
        low, high = 0, len(arr) - 1
        
        while low <= high:
            # If current range is already sorted,
            # smallest is at low
            if arr[low] <= arr[high]:
                return low
            
            mid = (low + high) // 2
            
            # If mid element > high element,
            # minimum is in the right half
            if arr[mid] > arr[high]:
                low = mid + 1
            # Otherwise minimum is at mid or in left half
            else:
                high = mid
        
        return low
class Solution {
    public int findKRotation(int[] arr) {
        int low = 0, high = arr.length - 1;
        
        while (low <= high) {
            // If current range is already sorted,
            // smallest is at low
            if (arr[low] <= arr[high])
                return low;
            
            int mid = (low + high) / 2;
            
            // If mid element > high element,
            // minimum is in the right half
            if (arr[mid] > arr[high])
                low = mid + 1;
            // Otherwise minimum is at mid or in left half
            else
                high = mid;
        }
        
        return low;
    }
}

Complexity Analysis

Time Complexity: O(log n)

At each iteration of the binary search, we halve the search space. Starting from n elements, we reach a single element in at most log₂(n) steps. For n = 10⁵, that's about 17 iterations — a massive improvement over the O(n) linear scan.

Space Complexity: O(1)

We only use a constant number of variables (low, high, mid). No recursion, no extra data structures.