Find Minimum in Rotated Sorted Array

1. Problem & Core Objective

A sorted array of distinct integers has been rotated some number of times. Return its minimum element in O(log n).

[3,4,5,1,2]        →  1     (rotated 3 times)
[4,5,6,7,0,1,2]    →  0     (rotated 4 times)
[11,13,15,17]      →  11    (not rotated at all)

Constraints: 1 <= n <= 5000 · values in [-5000, 5000] · all distinct · the array is a rotation of a sorted array

What's actually being tested: whether you compare against nums[hi] rather than nums[lo]. Both look plausible; only one handles the non-rotated case. It's the single most common bug in this family, and the reason two questions here are about rotation.

2. First-Principles Thought Process

What rotation does to the array

The array becomes two sorted runs, and — crucially — every element in the first run is larger than every element in the second. The minimum sits exactly at the boundary, the pivot.

So this is a boundary search: find where the array "drops".

The candidate comparison

Binary search needs a test at mid that says which half to keep. Two candidates:

Both work on a genuinely rotated array. Only one survives the non-rotated case.

Why nums[lo] fails

On [1,2,3,4,5] — a valid input, rotated zero times — nums[mid] = 3 > nums[lo] = 1. That looks like "I'm in the high run, search right", but the minimum is at index 0. You'd walk away from the answer.

Comparing against nums[hi] handles both shapes uniformly:

• nums[mid] > nums[hi] → mid is in the first run, so the pivot is strictly right → lo = mid + 1
• nums[mid] < nums[hi] → mid is in the second run (or the array isn't rotated), so the minimum is at mid or left of it → hi = mid

On a non-rotated array the second branch always fires and the range collapses to index 0. Correct without a special case.

Why hi = mid, not mid - 1

When nums[mid] < nums[hi], mid could itself be the minimum. Discarding it would lose the answer. That forces half-open bounds with lo < hi.

3. Solution Paths

Approach 1 — Linear scan (brute force)

public int findMin(int[] nums) {
    int min = nums[0];
    for (int v : nums) min = Math.min(min, v);
    return min;
}

• Time O(n) · Space O(1)

Counter-questions on this approach

⭐ "The array is nearly sorted and you're ignoring that. What structure is available?"

It's two sorted runs, which means a comparison at any index tells me which run I'm in — and therefore which side the pivot is on. That's enough to halve the search space each step. Scanning treats the input as unordered and throws that away.

"Could you at least stop early — the minimum is the first element that's smaller than its predecessor?"

Yes, and that's a genuine improvement on average. But the worst case is unchanged: a non-rotated array has no such drop, so you scan everything. Still O(n), and it violates the stated bound.

Approach 2 — Find the drop point (still linear)

public int findMin(int[] nums) {
    for (int i = 1; i < nums.length; i++) {
        if (nums[i] < nums[i - 1]) return nums[i];    // the pivot
    }
    return nums[0];                                    // never rotated
}

Scan for the one place the array decreases.

• Time O(n) · Space O(1)

Counter-questions on this approach

⭐ "This encodes the right idea — that there's exactly one drop. Why is it still too slow?"

Because it finds the drop by checking every adjacent pair. The drop's location is a boundary, and boundaries are what binary search finds in O(log n). I have the right mental model and the wrong search strategy.

"What does the fallback return nums[0] represent?"

The non-rotated case, where no drop exists. Notice it needs an explicit special case — and that the binary search version handles the same input with no special case at all. That's a small sign the binary search formulation is the more natural one.

Approach 3 — Binary search against nums[hi] (optimal)

public int findMin(int[] nums) {
    int lo = 0, hi = nums.length - 1;

    while (lo < hi) {                        // HALF-OPEN: lo == hi means we've found it
        int mid = lo + (hi - lo) / 2;

        if (nums[mid] > nums[hi]) lo = mid + 1;   // pivot is strictly right of mid
        else                      hi = mid;       // mid could BE the minimum
    }
    return nums[lo];
}

Trace — [4,5,6,7,0,1,2]:

Trace — [11,13,15,17], never rotated: every comparison takes the else branch, hi walks down to 0, and it returns nums[0] = 11. No special case needed.

• Time O(log n) · Space O(1)

Counter-questions on this approach

⭐ "Why compare against nums[hi] rather than nums[lo]? Both seem reasonable."

nums[lo] breaks on the non-rotated array. On [1,2,3,4,5], nums[mid] = 3 > nums[lo] = 1 looks like "I'm in the high run, search right" — but the minimum is at index 0, so you walk away from it.

nums[hi] is unambiguous: if nums[mid] > nums[hi] then mid must be in the first run, because in a sorted-or-rotated array no element of the second run exceeds the last element. Both rotated and non-rotated inputs are handled by the same two branches.

⭐ "Why hi = mid rather than hi = mid - 1?"

Because when nums[mid] < nums[hi], mid itself is a candidate for the minimum — it might be the pivot. hi = mid - 1 would discard it and lose the answer. That's why this uses half-open bounds with lo < hi, unlike an exact-match search.

"Can nums[mid] == nums[hi] happen?"

Not here — the values are guaranteed distinct, and mid < hi whenever lo < hi, so they're different elements with different values. That guarantee is doing real work: with duplicates the comparison becomes uninformative and the worst case degrades to O(n). That's LeetCode 154, in §7.

"How do you know the loop terminates?"

mid < hi always holds when lo < hi, since integer division rounds down. So hi = mid strictly decreases hi and lo = mid + 1 strictly increases lo. The range shrinks every iteration until lo == hi.

"Why return nums[lo] rather than tracking a running minimum?"

Because the invariant is that the minimum is always within [lo, hi]. When the range collapses to one element, that element is the minimum — no separate bookkeeping needed. Tracking a running min alongside would be redundant and would obscure the invariant.

Comparison

4. Why the Optimal Wins

The scan treats the array as unordered. The binary search exploits the one structural fact rotation preserves: the array is two sorted runs, and every comparison against the last element identifies which run you're in.

O(log n) is the floor, by the same argument as plain binary search — each comparison yields one bit, and locating the pivot among n positions needs log₂ n bits.

The transferable lesson is the failure mode, not the algorithm:

When two comparison anchors both look reasonable, test them against the degenerate input — here, zero rotations. The one that needs no special case is usually the right one.

5. Java Prerequisites

Half-open boundary search

while (lo < hi) {
    int mid = lo + (hi - lo) / 2;
    if (condition) lo = mid + 1;    // discard mid
    else           hi = mid;        // keep mid
}
return nums[lo];

hi = mid is safe because the loop condition is lo < hi — that guarantees mid < hi, so hi strictly decreases. With lo <= hi the same line is an infinite loop. See 01.

Overflow-safe midpoint — lo + (hi - lo) / 2. At n = 5000 it can't bite, but it's free.

6. Interview Communication Guide

Clarifying questions: Are values distinct (yes — with duplicates the bound degrades)? Could the rotation be zero (yes, and it's the case that breaks the naive comparison)? Return the value or its index?

The pitch

"Rotating a sorted array produces two sorted runs, where everything in the first run is larger than everything in the second. The minimum sits at the boundary between them — so this is a boundary search.

At each step I compare nums[mid] against nums[hi]. If nums[mid] > nums[hi], then mid must be in the first run, so the pivot is strictly to the right and I set lo = mid + 1. Otherwise mid is in the second run — or the array isn't rotated — so the minimum is at mid or left of it, and I set hi = mid.

The important detail is comparing against hi, not lo. On a non-rotated array like [1,2,3,4,5], nums[mid] > nums[lo] looks like a rotation and sends you right, away from the minimum at index 0. Comparing against hi handles rotated and non-rotated with the same two branches, no special case.

And hi = mid rather than mid - 1, because when nums[mid] < nums[hi], mid might itself be the minimum — discarding it would lose the answer.

O(log n) time, O(1) space."

Edge cases to volunteer:

The non-rotated case is the one to name before coding — it's the whole reason the comparison anchor matters, and stating it shows you chose nums[hi] deliberately rather than by luck.

7. Follow-Up Questions — Modified Constraints

⭐ "What if the array contained duplicates?" (LC 154)

The comparison becomes uninformative when nums[mid] == nums[hi] — you genuinely cannot tell which run you're in. Consider [3,3,1,3] versus [3,1,3,3]. The fix is to shrink the range by one (hi--) and retry, which is safe because nums[hi] is duplicated elsewhere so the minimum isn't lost.

That degrades the worst case to O(n) — an all-equal array forces n single steps. Worth stating plainly: duplicates don't just complicate the code, they break the logarithmic bound.

⭐ "Now search for an arbitrary target, not the minimum." (LC 33)

Find which half is sorted at each step, then check whether the target lies inside that half's range. Still O(log n). That's the next question.

"Return the number of rotations rather than the minimum."

It's the index of the minimum — the pivot position. Return lo instead of nums[lo]. No other change.

"What if you didn't know whether the array was rotated at all?"

No change — that's already handled. A non-rotated array is just a rotation by zero, and the algorithm returns index 0 without a special case. That robustness is a consequence of comparing against nums[hi].

"Find the maximum instead."

It's the element just before the pivot: nums[(lo - 1 + n) % n] once you've located the minimum at lo. The modulo handles the non-rotated case, where the maximum is the last element.