☕ DSA Java Articles

Topics › Binary Search › BS on 1D Arrays

Find out how many times the array is rotated

Easy TUF ID 84 A2Z

Java source ↗ Edit this article ↗

Problem

An array of n distinct integers was sorted in ascending order and then rotated to the right some number of times k, with 0 <= k < n. One right rotation moves the last element to the front. Given the rotated array nums, determine k.

Constraints: 1 ≤ n ≤ 10^5, all values distinct, values fit in a 32-bit signed integer.

Example 1

nums = [3, 4, 5, 1, 2]
answer = 3                // [1, 2, 3, 4, 5] rotated right 3 times

Example 2

nums = [4, 5, 6, 7, 0, 1, 2]
answer = 4                // [0, 1, 2, 4, 5, 6, 7] rotated right 4 times

Example 3

nums = [1, 2, 3, 4, 5]
answer = 0                // not rotated

The key observation turns this into a problem we already know how to solve. Rotating a sorted array right once moves the largest element to index 0 and shifts the minimum from index 0 to index 1. Rotating k times shifts the minimum to index k. So the number of rotations is the index of the minimum element. Check the examples: in [3, 4, 5, 1, 2] the minimum 1 is at index 3, and in [4, 5, 6, 7, 0, 1, 2] the minimum 0 is at index 4.

Approach 1: Brute force, index of the minimum by linear scan

Intuition. Find the position of the smallest element by looking at everything. Start with index 0 as the current best and replace it whenever a smaller value shows up. Distinct values mean the minimum, and therefore its index, is unique.

Algorithm.

  1. minIdx = 0.
  2. For i from 1 to n - 1: if nums[i] < nums[minIdx], set minIdx = i.
  3. Return minIdx.
static int bruteForce(int[] nums) {
    int minIdx = 0;
    for (int i = 1; i < nums.length; i++) {
        if (nums[i] < nums[minIdx]) minIdx = i;
    }
    return minIdx;
}

Complexity. Time O(n), space O(1).

Approach 2: Optimal, binary search tracking the index of the sorted half’s minimum

Intuition. A rotated sorted array consists of two ascending runs, and the minimum is the first element of the second run. For any range [lo, hi] with midpoint mid, at least one half is sorted, and nums[lo] <= nums[mid] tells us whether it is the left half [lo, mid]. The first element of a sorted half is that half’s minimum, so we record its index as a candidate and discard the whole half: nothing in it can beat its own first element. The other half contains the drop, so we continue there.

If the entire current range happens to be sorted (nums[lo] <= nums[hi]), its first index lo is the best candidate within the range and we can stop. For a non-rotated array this fires immediately with lo = 0.

The only difference from finding the minimum value is what we remember: the index instead of the value. We still compare values to decide which candidate is better.

Algorithm.

  1. lo = 0, hi = n - 1, minIdx = 0.
  2. While lo <= hi:
    • mid = lo + (hi - lo) / 2.
    • If nums[lo] <= nums[hi]: if nums[lo] < nums[minIdx], minIdx = lo; stop.
    • Else if nums[lo] <= nums[mid]: if nums[lo] < nums[minIdx], minIdx = lo; then lo = mid + 1.
    • Else: if nums[mid] < nums[minIdx], minIdx = mid; then hi = mid - 1.
  3. Return minIdx.
static int optimal(int[] nums) {
    int lo = 0, hi = nums.length - 1, minIdx = 0;   // index 0 is a valid first candidate
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (nums[lo] <= nums[hi]) {                   // whole range sorted: nums[lo] is its minimum
            if (nums[lo] < nums[minIdx]) minIdx = lo;
            break;
        }
        if (nums[lo] <= nums[mid]) {                  // left half sorted: nums[lo] is its minimum, drop it
            if (nums[lo] < nums[minIdx]) minIdx = lo;
            lo = mid + 1;
        } else {                                      // right half sorted: nums[mid] is its minimum, drop it
            if (nums[mid] < nums[minIdx]) minIdx = mid;
            hi = mid - 1;
        }
    }
    return minIdx;
}

Dry run on nums = [3, 4, 5, 1, 2]:

lo hi mid nums[lo] <= nums[hi]? sorted half candidate action
0 4 2 3 <= 2? no left (3 <= 5) nums[0] = 3, not < nums[0] lo = 3
3 4 3 1 <= 2? yes whole range nums[3] = 1 < 3: minIdx = 3 stop

Answer 3.

Complexity. Time O(log n), space O(1).

Starting minIdx at 0 is deliberate: nums[0] is a real element, so it is a legitimate initial candidate, and it saves a sentinel. Every later candidate replaces it only if strictly smaller, which is well defined because values are distinct.

Approach 3: Optimal, compare mid with the right end

Intuition. The compact variant maintains the invariant “the minimum’s index is in [lo, hi]” and needs no candidate variable. Compare nums[mid] with nums[hi]:

When lo == hi the invariant leaves exactly one possible index, and that is the rotation count.

Algorithm.

  1. lo = 0, hi = n - 1.
  2. While lo < hi: mid = lo + (hi - lo) / 2; if nums[mid] > nums[hi], lo = mid + 1; else hi = mid.
  3. Return lo.
static int optimalCompareRight(int[] nums) {
    int lo = 0, hi = nums.length - 1;
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (nums[mid] > nums[hi]) lo = mid + 1;       // the drop is strictly right of mid
        else hi = mid;                                // nums[mid] < nums[hi]: minimum is mid or left of it
    }
    return lo;
}

Dry run on nums = [4, 5, 6, 7, 0, 1, 2]:

lo hi mid nums[mid] nums[hi] action
0 6 3 7 2 7 > 2: lo = 4
4 6 5 1 2 1 < 2: hi = 5
4 5 4 0 1 0 < 1: hi = 4
4 4       lo == hi: return 4

Complexity. Time O(log n), space O(1).

The comparison must be against nums[hi], not nums[lo]. Against the left end, [1, 2, 3, 4, 5] and [3, 4, 5, 1, 2] both give nums[mid] > nums[lo] yet have their minimum on opposite sides. Against the right end the two inputs are told apart correctly, because the minimum is always in the run that ends at hi.

Edge cases and pitfalls