Find How Many Times a Sorted Array Has Been Rotated - Visualization

Arrays - Binary Search

Contents

VisualizationProblemExamplesSolutionAlgorithmCodeTimeSpace

Visualization Player

Problem Statement❯

Given a sorted and rotated array of distinct integers, your task is to determine the number of times the array has been rotated.

  • A rotation means shifting each element of the array to the right by one position.
  • The array was originally sorted in ascending order and then rotated.

Your goal is to find the index of the smallest element in the array, as this index represents the number of rotations.

If the array is empty, return -1.

Examples❯

Input Array Rotation Count Description
[15, 18, 2, 3, 6, 12] 2 Array was rotated 2 times. The smallest element 2 is at index 2.
[7, 9, 11, 12, 5] 4 Array was rotated 4 times. 5 is the smallest element at index 4.
[1, 2, 3, 4, 5] 0 No rotation. Array is already sorted.
[3, 4, 5, 1, 2] 3 Array rotated 3 times. Smallest element 1 at index 3.
[2] 0 Single element array, considered already sorted.
[] -1 Empty array, so no rotation count can be determined.

Solution❯

Understanding the Problem

We are given a sorted array that may have been rotated some number of times. Our task is to find out how many times it has been rotated.

For a beginner, let’s first understand what it means to rotate a sorted array.

Take a sorted array like [2, 3, 6, 12, 15, 18]. If we rotate it once to the right, it becomes [18, 2, 3, 6, 12, 15]. If we rotate it again, it becomes [15, 18, 2, 3, 6, 12]. So, rotation means shifting the elements around, and after some rotations, the smallest element moves from the beginning to somewhere else in the array.

So, our key insight is: the index of the smallest element tells us how many times the array has been rotated.

Step-by-Step Solution with Example

step 1: Understand the goal

We want to find the position of the minimum element in the array. That position equals the number of times the array was rotated.

step 2: Use Binary Search to find the smallest element

Instead of checking each element one by one (which takes linear time), we use binary search to reduce the time complexity to O(log n). We compare mid elements with their neighbors and adjust the search range accordingly.

step 3: Walkthrough with example [15, 18, 2, 3, 6, 12]

This array was originally [2, 3, 6, 12, 15, 18], and it has been rotated. Let's find how many times.

  1. Start with low = 0 and high = 5.
  2. Compute mid = (0 + 5) / 2 = 2. So arr[mid] = 2.
  3. Now check if arr[mid] is smaller than both its neighbors. It's smaller than 18 (arr[1]) and 3 (arr[3]), so it's the smallest element.
  4. Since the smallest element is at index 2, that’s our answer. The array was rotated 2 times.

step 4: Return the index of the smallest element

Once found, we return that index as the rotation count.

Edge Cases

Empty Array

If the input array is [], there are no elements to analyze. We return -1 to signal invalid input.

Single Element

In an array like [2], there’s only one element. It is already the smallest and largest, so we return 0 as no rotation is detectable.

Array not rotated

If the array is sorted but not rotated, like [1, 2, 3, 4], the smallest element is at index 0, so we return 0.

Array fully rotated (equal to its length)

If the array was rotated a number of times equal to its length, it returns to its original form. For example, rotating [1, 2, 3] three times gives [1, 2, 3] again. So again, the smallest element is at index 0, and the answer is 0.

Finally

This problem becomes easy once we understand that the rotation count is simply the index of the smallest element in the rotated array. By using binary search, we avoid unnecessary scanning and achieve a fast, elegant solution. Always remember to handle empty and minimal inputs for a robust implementation.

Algorithm Steps❯

  1. Initialize start = 0, end = n - 1.
  2. While start ≤ end:
  3. → If arr[start] ≤ arr[end], the subarray is already sorted, so return start.
  4. → Calculate mid = start + (end - start) / 2.
  5. → Calculate prev = (mid - 1 + n) % n and next = (mid + 1) % n.
  6. → If arr[mid] ≤ arr[prev] and arr[mid] ≤ arr[next], return mid.
  7. → If arr[mid] ≥ arr[start], search in the right half: start = mid + 1.
  8. → Else, search in the left half: end = mid - 1.

Code

C
C++
Python
Java
JS
Go
Rust
Kotlin
Swift
TS
#include <stdio.h>

int findRotationCount(int arr[], int n) {
    int start = 0, end = n - 1;
    while (start <= end) {
        if (arr[start] <= arr[end]) return start;
        int mid = start + (end - start) / 2;
        int next = (mid + 1) % n;
        int prev = (mid - 1 + n) % n;
        if (arr[mid] <= arr[prev] && arr[mid] <= arr[next])
            return mid;
        else if (arr[mid] >= arr[start])
            start = mid + 1;
        else
            end = mid - 1;
    }
    return 0;
}

int main() {
    int arr[] = {15, 18, 2, 3, 6, 12};
    int n = sizeof(arr)/sizeof(arr[0]);
    printf("Rotation Count: %d\n", findRotationCount(arr, n));
    return 0;
}

Time Complexity❯

CaseTime ComplexityExplanation
Best CaseO(1)When the array is not rotated, the first check detects it immediately.
Average CaseO(log n)Each iteration eliminates half the search space by applying binary search logic.
Worst CaseO(log n)In the worst case, the search continues until the pivot element is found using binary search.

Space Complexity❯

O(1)

Explanation: Only a constant number of variables (start, end, mid, next, prev) are used for the search.


Comments

💬 Please keep your comment relevant and respectful. Avoid spamming, offensive language, or posting promotional/backlink content.
All comments are subject to moderation before being published.

Loading comments...