Find Kth Rotation

You are given an array arr of distinct integers that was originally sorted in strictly increasing order, and then right-rotated k times. Your task is to find and return k — the number of rotations.

A single right rotation moves the last element to the front. Starting from [2, 4, 6, 9]:

After the 1st rotation: [9, 2, 4, 6]
After the 2nd rotation: [6, 9, 2, 4]

If the array was not rotated at all, return 0.

Hints

· Stuck? Reveal one nudge at a time.

Picture the original sorted array. After one right rotation, where does the largest element go — and where does the smallest end up after k rotations?

The rotation count is exactly the index of one special element. Which one, and why?

The array is two sorted runs glued at a single drop. Compare arr[mid] with arr[hi]: if arr[mid] is bigger, the drop is to the right; otherwise it is at mid or to the left. That one question halves the window — binary search it in O(log n).

Common doubts

Each right rotation moves the last element to the front. After k rotations, the last k elements of the sorted array occupy indices 0 .. k-1, so the original first element — the minimum — sits exactly at index k.

When the current window is already sorted (no drop inside it), arr[mid] < arr[hi] correctly says the minimum is at mid or to the left. Comparing against arr[lo] is ambiguous in that case — arr[mid] > arr[lo] holds both in a sorted window and when the drop is to the right, so it cannot tell the two apart.

The minimum is at index 0. The binary search naturally converges there: arr[mid] > arr[hi] is never true in a sorted array, so hi keeps shrinking to 0. No special case needed.

No. Floor division guarantees mid < hi whenever lo < hi, so hi = mid strictly decreases hi, and lo = mid + 1 strictly increases lo. The window shrinks every iteration.

Interview follow-ups

· What an interviewer asks next.

Ties break the halving argument: when arr[mid] == arr[hi] you cannot tell which side holds the drop, so you shrink conservatively with hi -= 1. The algorithm stays correct but degrades to O(n) in the worst case (e.g. all elements equal).

Two ways: find the pivot with this exact algorithm, then run a standard binary search in the correct sorted half — or use a single modified binary search that first determines which half of the window is sorted and checks whether the target lies inside it.

Reverse the first k elements, reverse the remaining n - k, then reverse the whole array — the classic three-reversal rotation trick, in O(n) time and O(1) space.

Fun facts

Rotating right k times is the same as rotating left n - k times — which is why the rotation count is always taken modulo n, and rotating n times lands you back where you started.
This find-the-pivot template is the warm-up for a whole family of problems — Search in Rotated Sorted Array and Minimum in Rotated Sorted Array are the same cliff hunt with one extra step bolted on.
The same drop-detection idea shows up in systems work: circular buffers and log-structured storage locate their oldest entry by finding exactly this kind of wrap-around point.

Asked at

AmazonMicrosoftAdobeOracle

Frequently Sometimes Occasionally

Example 1

Input: arr = [5, 1, 2, 3, 4]
Output: 1
The original sorted array is [1, 2, 3, 4, 5]. One right rotation moves 5 to the front, producing [5, 1, 2, 3, 4], so k = 1.

Example 2

Input: arr = [1, 2, 3, 4, 5]
Output: 0
The array is already sorted, so it was rotated 0 times.

Constraints

- 1 <= arr.size <= 10^5 - 1 <= arr[i] <= 10^7 - All elements of arr are distinct - arr is a sorted array rotated right k times, 0 <= k < arr.size

An array that was sorted, then quietly rotated — and your job is to recover how many turns it took. This problem is the gateway to binary search on rotated data: the answer falls out of one sharp observation, and the search template you build here gets reused in every rotated-array interview question.

Prerequisites

Before you start

· Concepts used directly in the solution.

Binary search. Halving a search window by asking one yes-or-no question per step — here the question is about structure, not a target value.

Rotated sorted arrays. A right rotation moves the last element to the front; k rotations move the last k elements to the front, in order.

Zero-based indexing. The answer is an index, so being exact about positions is the whole game.

Understand the problem

In plain English: arr was strictly increasing, someone rotated it right k times, and you must return k. Formally: given an array arr of n distinct integers that equals some sorted array rotated right k times (0 <= k < n), return k.

Worked example — arr = [5, 1, 2, 3, 4]

  5 | 1  2  3  4
    ^ the cliff: 5 -> 1 (the only place a value drops)

smallest element = 1, at index 1  ->  k = 1
original array: [1, 2, 3, 4, 5], rotated right once ✓

Clarifying questions

Two or three sharp questions before coding show you think in contracts, not just code.

Questions to ask first

· Signals seniority before you write a line of code.

Input validity

“Are all elements guaranteed to be distinct?”

Yes — and it matters. With duplicates, the comparison arr[mid] vs arr[hi] can tie, and the clean O(log n) argument degrades to O(n) in the worst case.

“Is the array always a genuine rotation of a sorted array?”

Yes. If the input could be arbitrary, a rotation count would not even be defined.

Edge cases

“What should I return if the array is not rotated at all?”

0 — the minimum already sits at index 0. Your algorithm must handle this without a special case.

“Can the array have just one element?”

Yes, n can be 1; the answer is 0.

Constraints and scale

“How large can the array be?”

Up to 10^5 elements. A linear scan passes, but the near-sorted structure is begging for an O(log n) binary search — that is what the interviewer wants to see.

The ideal opening — say it like this

Before I code, let me confirm the guarantees.

All elements are distinct, and the array is a true rotation of a strictly increasing array — correct?

If it is not rotated at all, I return 0, and a single-element array also returns 0.

Since the array is sorted except for one break point, I will aim for an O(log n) binary search instead of a linear scan.

Key observations

1Aha

The rotation count is the index of the minimum

Each right rotation moves the last element to the front. After k rotations, the last k elements of the sorted array occupy indices 0 .. k-1, and the original first element — the minimum — lands exactly at index k. Find the minimum's position and you have found k.

2Aha

There is exactly one cliff

A rotated sorted array of distinct values is two increasing runs glued together. Reading left to right, values climb, drop once, then climb again — and if k = 0, they never drop at all.

[4, 5, 6, 1, 2, 3]
 ──climb──╮
          ╰──climb──
     one drop: 6 -> 1, right before the minimum

3Aha

Comparing arr[mid] with arr[hi] locates the cliff

Pick any mid. If arr[mid] > arr[hi], the order broke somewhere after mid, so the minimum lives strictly to the right. Otherwise the segment mid .. hi is sorted, so the minimum is at mid or to its left. One comparison discards half the array — that is a binary search, even though we are not searching for a value.

Brute force vs optimal

	Brute force	Optimal
Idea	Scan for the minimum	Binary search for the cliff
Time	O(n)	O(log n)
Space	O(1)	O(1)

Both approaches are implemented in full — with traces and pitfalls — in the Approaches selector below.

Summary

Key takeaway

A rotated sorted array is two sorted runs glued at a single cliff, and the minimum sits right after it — at index k. One comparison of arr[mid] against arr[hi] tells you which half hides that cliff, so binary search finds it in O(log n). Binary search on structure, not on a value — the template behind every rotated-array problem.

lo = 0, hi = n - 1
while lo < hi:
    mid = (lo + hi) / 2
    if arr[mid] > arr[hi]:  lo = mid + 1    (cliff is to the right)
    else:                   hi = mid        (min is at mid or left)
return lo                                   (index of the minimum = k)