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, Python, C++ and JavaScript, 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.

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (2 examples, or your own). Submit also runs 11 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

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.

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 code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Linear scan for the minimumO(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.

  1. Track the index of the minimum.
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].

  1. lo = 0, hi = n - 1.
  2. If arr[mid] > arr[hi], the minimum is right of mid: lo = mid + 1. Else hi = mid.
  3. Return lo.
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.