Find How Many Times Array is Rotated

Easy Binary Search Rotated Array Original on GeeksforGeeks

Find How Many Times Array is Rotated is a easy binary search problem solved with the rotated array pattern. The best approach, optimal (binary search against the last element), runs in O(log n) time and O(1) space. Below are 2 approaches in Java, from linear scan for the minimum up.

Problem

A sorted array of distinct values was rotated to the right some number of times. Return how many times it was rotated.

Examples

Example 1

Input: arr = [15, 18, 2, 3, 6, 12]
Output: 2
Why: The smallest value 2 sits at index 2, so the sorted array was rotated right twice.

Example 2

Input: arr = [7, 9, 11]
Output: 0

Constraints

1 <= arr.length <= 10^5, distinct values.
A sorted array rotated right some number of times.

Animated walkthrough

A narrated, step-by-step animation that builds the solution from the idea up. Press play, or step through it at your own pace.

Concepts first, then the problem and every approach, step by step.

Code

Code appears here once we start writing it.

Space to play or pause · ← → to jump a step · click or drag the bar to seek

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the Java code.

Approach	Time	Space
Linear scan for the minimum	`O(n)`	`O(1)`
Optimal (binary search against the last element)	`O(log n)`	`O(1)`

1Linear scan for the minimum

TimeO(n)

SpaceO(1)

The index of the smallest element is the rotation count.

Track the index of the minimum.

Java

class Solution {
    public int findKRotation(int[] arr) {
        int idx = 0;
        for (int i = 1; i < arr.length; i++) if (arr[i] < arr[idx]) idx = i;
        return idx;
    }
}

2Optimal (binary search against the last element)

TimeO(log n)

SpaceO(1)

Every value in the right sorted part is <= the last element, and every value in the left part is greater. Find the first index whose value is <= arr[n - 1].

lo = 0, hi = n - 1.
If arr[mid] > arr[hi], the minimum is right of mid: lo = mid + 1. Else hi = mid.
Return lo.

Java

class Solution {
    public int findKRotation(int[] arr) {
        int lo = 0, hi = arr.length - 1;
        while (lo < hi) {
            int mid = (lo + hi) >>> 1;
            if (arr[mid] > arr[hi]) lo = mid + 1;
            else hi = mid;
        }
        return lo;
    }
}

Edge cases to test

Not rotated at all
Rotated by n - 1

Hints

Hint 1

The rotation count equals the index of the minimum element.

FAQ

What is the best time complexity for Find How Many Times Array is Rotated?

Optimal (binary search against the last element) runs in O(log n) time and O(1) extra space.

Which pattern does Find How Many Times Array is Rotated use?

It is a binary search problem that uses the rotated array pattern. Other problems with the same pattern: Find Minimum in Rotated Sorted Array, Find Minimum in Rotated Sorted Array II, Search in Rotated Sorted Array.

Is there a brute force solution for Find How Many Times Array is Rotated?

Yes. Linear scan for the minimum takes O(n) time and O(1) space. The index of the smallest element is the rotation count.

Which edge cases should I test for Find How Many Times Array is Rotated?

Not rotated at all; Rotated by n - 1.