Find Rotation Count in Sorted Array

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.

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.

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.

#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;
}

#include <iostream>
using namespace std;

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]);
    cout << "Rotation Count: " << findRotationCount(arr, n) << endl;
    return 0;
}

def find_rotation_count(arr):
    n = len(arr)
    start, end = 0, n - 1
    while start <= end:
        if arr[start] <= arr[end]:
            return start
        mid = start + (end - start) // 2
        next_idx = (mid + 1) % n
        prev_idx = (mid - 1 + n) % n
        if arr[mid] <= arr[prev_idx] and arr[mid] <= arr[next_idx]:
            return mid
        elif arr[mid] >= arr[start]:
            start = mid + 1
        else:
            end = mid - 1
    return 0

arr = [15, 18, 2, 3, 6, 12]
print("Rotation Count:", find_rotation_count(arr))

public class RotationCountFinder {
  public static int findRotationCount(int[] arr) {
    int n = arr.length;
    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;
  }
  public static void main(String[] args) {
    int[] arr = {15, 18, 2, 3, 6, 12};
    System.out.println("Rotation Count: " + findRotationCount(arr));
  }
}

function findRotationCount(arr) {
  let n = arr.length;
  let start = 0, end = n - 1;
  while (start <= end) {
    if (arr[start] <= arr[end]) return start;
    let mid = Math.floor(start + (end - start) / 2);
    let next = (mid + 1) % n;
    let 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;
}

let arr = [15, 18, 2, 3, 6, 12];
console.log("Rotation Count:", findRotationCount(arr));

package main

import "fmt"

func findRotationCount(arr []int) int {
    n := len(arr)
    start, end := 0, n-1
    for start <= end {
        if arr[start] <= arr[end] {
            return start
        }
        mid := start + (end-start)/2
        next := (mid + 1) % n
        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
}

func main() {
    arr := []int{15, 18, 2, 3, 6, 12}
    fmt.Println("Rotation Count:", findRotationCount(arr))
}

fn find_rotation_count(arr: &[i32]) -> usize {
    let n = arr.len();
    let (mut start, mut end) = (0, n - 1);
    while start <= end {
        if arr[start] <= arr[end] {
            return start;
        }
        let mid = start + (end - start) / 2;
        let next = (mid + 1) % n;
        let prev = (mid + n - 1) % 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;
        }
    }
    0
}

fn main() {
    let arr = vec![15, 18, 2, 3, 6, 12];
    println!("Rotation Count: {}", find_rotation_count(&arr));
}

fun findRotationCount(arr: IntArray): Int {
    val n = arr.size
    var start = 0
    var end = n - 1
    while (start <= end) {
        if (arr[start] <= arr[end]) return start
        val mid = start + (end - start) / 2
        val next = (mid + 1) % n
        val 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
}

fun main() {
    val arr = intArrayOf(15, 18, 2, 3, 6, 12)
    println("Rotation Count: ${findRotationCount(arr)}")
}

func findRotationCount(_ arr: [Int]) -> Int {
    let n = arr.count
    var start = 0, end = n - 1
    while start <= end {
        if arr[start] <= arr[end] { return start }
        let mid = start + (end - start) / 2
        let next = (mid + 1) % n
        let 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
}

let arr = [15, 18, 2, 3, 6, 12]
print("Rotation Count: \(findRotationCount(arr))")

function findRotationCount(arr: number[]): number {
  let n = arr.length;
  let start = 0, end = n - 1;
  while (start <= end) {
    if (arr[start] <= arr[end]) return start;
    let mid = Math.floor(start + (end - start) / 2);
    let next = (mid + 1) % n;
    let 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;
}

let arr: number[] = [15, 18, 2, 3, 6, 12];
console.log("Rotation Count:", findRotationCount(arr));

Time complexity

Space complexity

O(1)

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