p34 — Find Minimum in Rotated Sorted Array

Source: LeetCode 153 · Medium · Topics: Array, Binary Search Companies (2024–2025 frequency): Amazon (high), Meta (high), Google (high), Microsoft (medium), Apple (medium) Loop position: algorithm round. Often paired with p33 (Search in Rotated Sorted Array) in the same loop — interviewer asks p34 first, then extends to p33.

1. Quick Context

Given a sorted ascending array of distinct integers that has been rotated at an unknown pivot, return the minimum element. Required: O(log N).

The minimum is the rotation pivot itself — the only element where nums[i-1] > nums[i] (or index 0 if not rotated).

The discriminator: the right invariant is tighter than p33’s. Compare nums[mid] to nums[hi] (NOT nums[lo]):

• If nums[mid] > nums[hi], the pivot is STRICTLY to the right of mid → lo = mid + 1.
• Else, the pivot is at mid or to the left → hi = mid.

Loop condition is while lo < hi (not <=). The loop terminates when lo == hi, which IS the pivot index.

Many candidates botch this by reusing the p33 template (while lo <= hi, comparing to nums[lo]). The result: extra cases, off-by-one bugs, and a longer interview.

2. LeetCode Link + Attempt Gate

🔗 https://leetcode.com/problems/find-minimum-in-rotated-sorted-array/

STOP. 20-min timer. Try to derive the invariant from scratch — don’t paste the p33 template.

3. Prerequisite Concepts

• Plain binary search.
• The mental picture of a rotated sorted array (two ascending runs).
• The convergent-bounds pattern: while lo < hi, narrow toward a single answer index.

4. How to Approach (FRAMEWORK Steps 1–9)

Step 1 — Restate: “Distinct sorted array rotated at unknown pivot. Return min in O(log N).”

Step 2 — Clarify:

• “Distinct values?” (Yes for LC 153. LC 154 is duplicates — different.)
• “Could be unrotated?” (Yes — min is then nums[0].)
• “Empty array?” (No per spec — N ≥ 1.)
• “Required O(log N)?” (Yes.)

Step 3 — Constraints: N ≤ 5000 typically; the O(log N) requirement is binding.

Step 4 — Examples:

• [3,4,5,1,2] → 1.
• [4,5,6,7,0,1,2] → 0.
• [11,13,15,17] → 11 (unrotated).
• [2,1] → 1.
• [1] → 1.

Step 5 — Brute Force: Linear min(nums) is O(N). State and pivot.

Step 6 — Complexity: O(log N) time, O(1) space.

Step 7 — Pattern Recognition:

• “Find a discontinuity in a near-sorted array, O(log N)” → binary search with a convergent-bounds pattern (while lo < hi).
• “Compare to the right endpoint” — the asymmetry is the key. Anchoring on nums[hi] gives a single clean invariant; anchoring on nums[lo] requires extra cases.

Step 8 — Develop: see solution.py.

Step 9 — Test: unrotated, rotated by 1, rotated by N-1, two-element, single-element, large rotations.

5. Progressive Hints

If stuck for 5 min, open hints.md.

6. Deeper Insight — Why anchor on nums[hi], not nums[lo]?

6.1 The invariant

In a rotated sorted array (distinct), the minimum (= pivot) has a clean characterization: it is the leftmost index p such that nums[p] <= nums[len-1]. The function f(i) = (nums[i] <= nums[len-1]) is monotonic over i — False, False, ..., False, True, True, ..., True — with the boundary AT the pivot. This is the classic “find first True in a Boolean monotonic predicate” pattern, perfectly suited to convergent binary search.

6.2 The decision rule

At any mid:

• If nums[mid] > nums[hi], then mid is in the LEFT sorted run (before the pivot). The pivot must be strictly to the right → lo = mid + 1.
• Else (nums[mid] <= nums[hi]), then mid is in the RIGHT sorted run (at or after the pivot). The pivot could be at mid or to the left → hi = mid (NOT mid - 1 — we might lose the answer).

One comparison, two cases, both narrow strictly. No third “found it” case — the loop runs until lo == hi.

6.3 Why while lo < hi (not <=)

When lo == hi, we’ve converged on the answer index. With <, the loop exits with lo == hi == pivot. With <=, we’d loop once more with mid == lo == hi, then narrow to an invalid state. The < form is the convergent-bounds idiom; memorize it.

6.4 Why NOT compare to nums[lo]

If we compare to nums[lo], the analysis splits into three subcases (unrotated, mid in left run, mid in right run) — the unrotated case must be specially handled. Compare to nums[hi] and unrotated works automatically (the whole array is <= nums[hi], so we always narrow hi = mid, ending at index 0).

6.5 Duplicates (LC 154)

With duplicates, nums[mid] == nums[hi] doesn’t tell us which run we’re in. Example: nums = [1,1,1,0,1], mid=2, hi=4 — both 1. Fix: when nums[mid] == nums[hi], do hi -= 1 (we lose one position but it’s safe — the pivot is still in [lo, hi-1] because nums[hi] is duplicated somewhere). Worst case O(N).

6.6 Connection to “binary search on answer”

Convergent bounds (while lo < hi) is the structural sibling of binary search on answer (LC 410, LC 875, LC 1011 — see Phase 02 Lab 04). Both narrow a continuous range using a monotonic predicate. p34 is the simplest possible instance of this template applied to an index range.

7. Anti-Pattern Analysis

1. Reusing the p33 template (compare to nums[lo], while lo <= hi). Works, but bloated with cases. The cleaner template here is while lo < hi and nums[mid] vs nums[hi].
2. hi = mid - 1 instead of hi = mid. Loses the answer when nums[mid] IS the minimum.
3. while lo <= hi. Causes an extra iteration past convergence, where mid == lo == hi and the inequality logic becomes vacuous (or infinite-loops if you also use hi = mid).
4. Special-casing the unrotated array (if nums[0] < nums[-1]: return nums[0]). Unnecessary — the convergent loop handles it.
5. Returning nums[lo] AND nums[hi] from inside the loop without convergence. The loop must end naturally; reading mid-iteration is wrong.
6. Confusing pivot-index with min-value. The problem asks for the VALUE (nums[lo]), not the index. Read carefully.
7. Linear scan min(nums). O(N) — violates the O(log N) requirement.
8. Reaching for LC 154 (duplicates) code on the LC 153 problem. Slower than necessary and signals you don’t recognize the simpler invariant.

8. Skills & Takeaways

• Convergent-bounds binary search (while lo < hi, hi = mid) — burn this template.
• The nums[mid] vs nums[hi] anchor — memorize the direction.
• Monotonic-predicate framing — recognize that “first True in f(i) = nums[i] <= nums[N-1]” is the same as p34.
• Knowing when to break the symmetry (left vs right anchor) — design choice, not arbitrary.
• Setup for LC 154 (duplicates) and p35 (median of two sorted — binary search on partition).

9. When to Move On

Move on when:

• You can write the 6-line solution in under 5 min with correct boundaries.
• You can explain why nums[hi] (not nums[lo]) is the anchor.
• Your stress test passes 300 random rotated arrays vs min(nums) oracle.
• You can derive the LC 154 (duplicates) variant on demand.
• You can apply the same template to LC 162 (Find Peak Element) and binary-search-on-answer problems.

10. Company Context

Amazon:

• Top-5 most-asked “binary search” Medium at Amazon in 2024-25. Often the first Q in the algo loop, followed by p33 as the senior extension.
• Scorecard phrase: “Strong — clean convergent-bounds binary search.”

Meta:

• Common warmup or “tie-breaker” Medium. Bar Raiser may chain into LC 154 (duplicates) for senior candidates.
• Scorecard phrase: “Strong — recognized the monotonic-predicate framing.”

Google:

• Often appears in algo loops paired with p35 (median) — Google likes the “binary search beyond simple lookup” theme.
• Scorecard phrase: “Algorithm — clean convergent binary search, articulated invariant.”

Microsoft:

• Standard L62 binary search question. Bar Raiser cares about clean code and boundary correctness.
• Scorecard phrase: “Solid — convergent binary search with correct boundaries.”

Apple:

• Less frequent but appears in systems/firmware loops where rotated-buffer search is a real concern.
• Scorecard phrase: “Pragmatic — binary search applied to rotated data.”

11. Interviewer’s Lens

12. Level Delta

Mid (L4):

• Convergent binary search.
• Correct boundary, while lo < hi.
• Tests rotated and unrotated.

Senior (L5):

• Same + clean articulation of the monotonic-predicate framing.
• Explains why nums[hi] is the right anchor.
• Anticipates and discusses LC 154 (duplicates) worst case.

Staff (L6):

• Connects to binary-search-on-answer template (LC 410, LC 875).
• Connects to LC 162 (Find Peak Element) — same convergent template, different predicate.
• Discusses production: clock-wraparound in distributed time series, log-structured storage indices.

Principal (L7+):

• Discusses branchless binary search and cache effects (Khuong & Morin 2017, Eytzinger layout).
• Discusses galloping search for unknown-position bounded queries (Timsort, libstdc++).
• Discusses algorithm design as predicate engineering: “binary search isn’t about the loop; it’s about identifying a monotonic predicate over the answer space.”

13. Follow-up Q&A

Q1: What if duplicates are allowed? (LC 154) A: When nums[mid] == nums[hi], we can’t tell which run mid is in. Safe fix: hi -= 1. The pivot must still be in [lo, hi-1] because nums[hi] is duplicated elsewhere in the range. Worst case O(N) on [1,1,1,...,0,1].

Q2: Return the pivot INDEX, not the value. A: Same loop; return lo instead of nums[lo].

Q3: Find peak in a bitonic array. (LC 162) A: Convergent binary search with predicate nums[mid] < nums[mid+1]. If yes, peak is to the right (lo = mid + 1); else, peak is at mid or left (hi = mid). Same template, different predicate.

Q4: Find first/last position of a target in a sorted array. A: Two convergent searches with different bias. The “first” search uses nums[mid] >= target as the predicate; “last” uses nums[mid] > target then subtracts 1. LC 34.

Q5: 2D rotated matrix — each row independently rotated. A: Apply p34 per row, O(M log N).

14. Solution Walkthrough

See solution.py:

• find_min(nums) — convergent binary search, O(log N).
• find_min_brute(nums) — min(nums). Oracle.
• stress_test() — 300 random sorted arrays (length 1..20) rotated by random k.
• edge_cases() — single element, unrotated, two-element, rotated by 1 and N-1, large rotations, with negatives.

Run: python3 solution.py.

15. Beyond the Problem

Principal-engineer code review comment:

“The whole point of this problem is the elegance of the convergent-bounds template. Resist the urge to add the if nums[0] < nums[-1]: return nums[0] ‘optimization’ — it adds a branch, hides the invariant, and saves zero asymptotic time. The clean version reads exactly the way the invariant proves: ‘find first index where nums[i] <= nums[N-1]’. Anyone refactoring this code later will appreciate the lack of special cases. Second: in a code review, ask whether the function should return the index or the value — the LC problem says value, but a real internal API often wants both. Make the contract explicit. Third: if you find yourself writing duplicate variants of this function for LC 153 and LC 154, extract a single function with a duplicates_allowed parameter — DRY beats clever per-problem rewrites.”

Connections forward:

• p33 — Search in Rotated Sorted Array: harder cousin, same array shape.
• p35 — Median of Two Sorted Arrays: binary search on partition — different predicate space.
• LC 154 — Find Min in Rotated Sorted Array II: duplicates variant.
• LC 162 — Find Peak Element: same convergent template.
• LC 410 — Split Array Largest Sum: binary search on answer (Phase 02 Lab 04).
• LC 875 — Koko Eating Bananas: same family.
• Phase 02 Lab 04 — Binary Search on Answer: full template lab.
• Production: clock-wraparound search in distributed time series, log-structured storage indexing.