Rotation Count (How Many Times a Sorted Array Was Rotated)

Rotation Count is a Modified Binary Search problem equivalent to finding the index of the smallest element in a rotated sorted array, because the number of rotations equals that index. We binary-search comparing the middle element with its neighbours to locate the single point where an element is smaller than its predecessor, which is the minimum, and its index is the rotation count.

What is the problem?

Rotation Count (How Many Times a Sorted Array Was Rotated). Given an ascending sorted array that has been rotated an unknown number of times, count how many times it was rotated, which equals the index of its smallest element. Explain how binary search locates the minimum.

How does the approach work?

We binary-search with start = 0 and end = n - 1. At each step mid = start + (end - start) / 2. We compare arr[mid] with arr[end]: if arr[mid] > arr[end] the minimum must be to the right of the middle, so start = mid + 1; otherwise the minimum is at the middle or to its left, so end = mid. For example, if (arr[mid] > arr[end]) start = mid + 1; else end = mid;. The loop runs while start < end, and when it ends start points at the minimum, so start is the rotation count.

Comparing with the right end rather than the left end is the robust choice because it correctly handles the case where the array is not rotated at all, in which case the minimum is at index zero and the comparison keeps moving end left until start equals zero. If the array is fully sorted and un-rotated, the answer is zero rotations.

A senior nuance is that with duplicate values the arr[mid] > arr[end] test can be inconclusive when they are equal, in which case we decrement end by one, which can degrade to O(n); with distinct values the search is strictly logarithmic. Returning start directly gives both the minimum's index and the rotation count in one value. Complexity is O(log n) time with distinct values and O(1) space.

What is the banking use case?

The code defines a RotationCountService exposing countRotations(serials) returning the rotation count. A Demo counts rotations of a rotated serial array and logs the result.

How do you implement this in Java?

// ─── File: src/main/java/com/bank/rotate/service/RotationCountService.java ───
package com.bank.rotate.service;

import java.util.logging.Logger;

// Counts rotations = index of the minimum in a rotated sorted array.
public class RotationCountService {
    private static final Logger log = Logger.getLogger(RotationCountService.class.getName());

    public int countRotations(int[] serials) {
        int start = 0, end = serials.length - 1;
        while (start < end) {
            int mid = start + (end - start) / 2;
            if (serials[mid] > serials[end]) start = mid + 1; // min is to the right
            else end = mid;                                    // min is here or left
        }
        final int count = start; // index of minimum == rotation count
        log.info(() -> "Array rotated " + count + " times (min at index " + count + ")");
        return count;
    }
}

// ─── File: src/main/java/com/bank/rotate/RotationCountApplication.java ───
package com.bank.rotate;

import com.bank.rotate.service.RotationCountService;
import java.util.logging.Logger;

public class RotationCountApplication {
    private static final Logger log = Logger.getLogger(RotationCountApplication.class.getName());

    public static void main(String[] args) {
        RotationCountService service = new RotationCountService();
        int[] serials = {40, 50, 60, 10, 20, 30}; // rotated 3 times
        log.info("Cheque serials rotation count: " + service.countRotations(serials));
    }
}

What is the project structure?

rotation-count-service/
├── pom.xml
├── src/
│   ├── main/
│   │   ├── java/com/bank/rotate/
│   │   │   ├── RotationCountApplication.java     (main class)
│   │   │   └── service/
│   │   │       └── RotationCountService.java
│   │   └── resources/
│   │       └── application.yml
│   └── test/
│       └── java/com/bank/rotate/
│           └── RotationCountServiceTest.java

How do you build and run?

# Build
mvn clean package -DskipTests

# Run
java -jar target/rotation-count-service-1.0.0.jar

# See convergence at FINE level
java -Djava.util.logging.ConsoleHandler.level=FINE \
  -jar target/rotation-count-service-1.0.0.jar

What is the step-by-step walkthrough?

Input: serials 40, 50, 60, 10, 20, 30.

Oct 27, 2026 10:39:07 PM com.bank.rotate.service.RotationCountService countRotations
INFO: Array rotated 3 times (min at index 3)
INFO: Cheque serials rotation count: 3

What is the high-level design?

  ═══ HLD — Cheque Serial Rotation Count (Banking) ═══

  ┌────────────┐ HTTPS ┌──────────────┐ REST ┌─────────────────────┐
  │ Recon Tool │──────→│ API Gateway  │─────→│ Rotation Count ×2   │
  └────────────┘       │ (JWT, rate)  │      │ (Spring Boot)       │
                       └──────────────┘      └─────────┬───────────┘
                                                      │ load serial batch
                                                      ▼
                                           ┌─────────────────────┐
                                           │ PostgreSQL serials   │
                                           └─────────────────────┘

What is the low-level design?

  ═══ LLD — Rotation Count ═══

  ┌─ Design Patterns Used ──────────────────────────────────┐
  │  Binary search for minimum via compare-with-right-end    │
  │     WHY: min index equals the rotation count             │
  └──────────────────────────────────────────────────────────┘

  ┌─ SOLID Principles Applied ──────────────────────────────┐
  │  S: service only counts rotations                        │
  │  O: any rotation amount works unchanged                  │
  │  D: depends only on primitive int array                  │
  └──────────────────────────────────────────────────────────┘

  ── Class Diagram ──────────────────────────────────────────
  ┌──────────────────────────────────────┐
  │ RotationCountService                  │
  │ ───────────────────────────────────── │
  │ + countRotations(serials): int        │
  └──────────────────────────────────────┘

  ── State: [start,end] converge on min index ──────────────
  compare mid with end to pick the half holding the min

  Contract for countRotations(serials):
    Pre:  distinct, ascending then rotated
    Post: index of minimum = number of rotations (0 if none)

What is the time and space complexity?

Analyze the solution based on the algorithm used. Consider both the time to process input and the space required for any data structures.

What are common mistakes?

Common mistakes include off-by-one errors, not handling edge cases like empty input, and not considering the constraints of the problem.

What are the edge cases?

Edge cases include empty input, single element input, all identical elements, and boundary values.

What should a senior engineer know?

A senior engineer should understand the time-space tradeoffs, be able to explain the algorithm clearly, and know when this technique applies versus alternatives.