parikshan

find-min-in-rotated-sorted-array

Difficulty: Medium  ·  Topic: Binary Search  ·  Practice it on parikshan: /practice/find-min-in-rotated-sorted-array/start

The story

A Kafka consumer group restarts after a crash and needs to find the earliest unacknowledged offset in a partition. The partition's log is segmented by timestamp; the segments are stored on disk and the index of segments is sorted by timestamp, modulo a rotation because a stale broker's clock jumped backward at 03:14 UTC and the rotated portion came online after that. The consumer cannot afford an O(n) scan of millions of segments; it has milliseconds before it falls further behind.

Finding the minimum of a rotated sorted array is the canonical version of that lookup. It is also the first binary-search problem where the array is not monotone end-to-end. The skill is rephrasing it as a binary search on a predicate that is monotone. Once you see that, the rest of the Binary Search cluster opens up.

What's actually being asked

You are given an array of distinct integers that was originally sorted ascending, then rotated by some unknown amount k in [0, n). For example, [1, 2, 3, 4, 5] rotated by 3 becomes [4, 5, 1, 2, 3]. Return the minimum element in O(log n) time.

The naive approach

Linear scan, min(nums). O(n). Works on any array, ignores the rotation structure. For n = 10^6 that is one million comparisons; for the Kafka consumer above, one million per partition per restart. Unacceptable.

The key insight

The array is not sorted, but a predicate over its indices is monotone. Define:

P(i) = "nums[i] <= nums[n-1]"

On a non-rotated array (k = 0), P(i) is True everywhere. On a rotated array, the rightmost segment from the rotation point to the end is the "small" half, and the left segment from index 0 up to the rotation point minus one is the "large" half. Concretely, P is FFFF...TTTT with the boundary at the rotation point. The minimum sits at the first True.

That is the first-bad-version template against the right end of the array. The trick is choosing nums[hi] (or in the half-open form, nums[n-1]) as the reference, not nums[lo]. Comparing with nums[lo] is the classic trap: in the non-rotated case P(i) would flip, and the search would mis-converge.

Step-by-step approach

The half-open lower-bound template, with the predicate nums[mid] <= nums[hi-1] shortcut: we compare with nums[hi] while keeping hi as the inclusive right end, because tracking nums[hi-1] mid-loop is awkward. The closed-form variant below is the standard expression:

def find_min(nums):
    lo, hi = 0, len(nums) - 1          # closed; both ends are legal answers
    while lo < hi:
        mid = (lo + hi) // 2
        if nums[mid] > nums[hi]:       # mid is in the LARGE half → answer is right of mid
            lo = mid + 1
        else:                          # mid is in the SMALL half → answer is at mid or earlier
            hi = mid                   # NOT mid - 1 (mid itself could be the answer)
    return nums[lo]

Loop invariant in English: the minimum lies in nums[lo..hi] (inclusive on both sides). Each iteration shrinks the window strictly.

The crucial line is hi = mid, not hi = mid - 1. The minimum could BE nums[mid]; you cannot exclude it. This is the half-open spirit creeping into a closed-form template; respect it.

Worked example

nums = [4, 5, 6, 7, 0, 1, 2]

Reference: nums[hi] = 2 throughout (since hi moves but nums[hi] happens to stay <= reference once we converge).

  • lo=0, hi=6. mid=3, nums[3]=7. 7 > 2 → lo=4.
  • lo=4, hi=6. mid=5, nums[5]=1. 1 ≤ 2 → hi=5.
  • lo=4, hi=5. mid=4, nums[4]=0. 0 ≤ 1 → hi=4.
  • lo=4, hi=4 → exit. Return nums[4] = 0. ✓

Counter-case: nums = [1, 2, 3, 4, 5] (no rotation).

  • lo=0, hi=4. mid=2, nums[2]=3. 3 ≤ 5 → hi=2.
  • lo=0, hi=2. mid=1, nums[1]=2. 2 ≤ 3 → hi=1.
  • lo=0, hi=1. mid=0, nums[0]=1. 1 ≤ 2 → hi=0.
  • lo=0, hi=0 → exit. Return nums[0] = 1. ✓

The same template handled the rotated and non-rotated cases without a special branch. That is what comparing with nums[hi] (not nums[lo]) bought you.

Complexity

  • Time: O(log n).
  • Space: O(1).

Common pitfalls

  1. Comparing with nums[lo]. On a non-rotated array, nums[mid] > nums[lo] is True for every mid > 0, which sends the search to the right and never finds index 0. The reference must be the right end, not the left.
  2. hi = mid - 1. Wrong. The minimum can BE nums[mid], so you cannot exclude mid. The closed-form half-open hybrid in the template is the canonical fix.
  3. Forgetting distinctness. The variant find-min-in-rotated-sorted-array-ii allows duplicates; with duplicates, nums[mid] == nums[hi] cannot decide which side holds the minimum. The fix is hi -= 1 (slow worst case, O(n)). For this problem, distinctness is guaranteed, so the strict comparison is safe.
  4. Returning lo instead of nums[lo]. The spec asks for the value, not the index. Read it.

Where this shows up in the enterprise

  • Kafka log compaction: finding the earliest offset whose timestamp is in a queried range when segments are rotated by a clock-skew event.
  • TigerBeetle ledger consistency check: locating the boundary between two epochs after a rotated import.
  • AWS S3 versioned bucket rollback: smallest version-id whose timestamp is after a corruption event.
  • Cloudflare KV regional sync: the boundary between pre-sync and post-sync writes after a rotated replay.
  • CockroachDB / Spanner timestamp catch-up: the first commit at or after a HLC checkpoint when commits arrived out of clock order.
  • Apple iCloud calendar sync: the first event in a feed that was rotated after a midnight UTC reset.

The shape is always the same: a once-monotone sequence that has been cut and rotated, with a need to find the wrap-around point.

Variants you'll see elsewhere

  • search-in-rotated-sorted-array: same rotation, but you are searching for a specific target, not the minimum. The "which half is sorted" predicate generalises this idea.
  • find-min-in-rotated-sorted-array-ii: allows duplicates. Worst-case becomes O(n).
  • find-rotation-count: returns k, the rotation amount. Same loop, return lo instead of nums[lo].
  • find-peak-element: not rotation but the same spirit: a non-monotone array where a monotone predicate over slopes lets you binary-search.
  • first-bad-version: pure form of the predicate without an array.

How parikshan turns this into a learning loop

This is the problem where the binary-search template stops being a memorised loop and starts being a tool. Recommended sequence on parikshan:

  1. Solve binary-search, search-insert-position, and first-bad-version first. That locks the template.
  2. Open this problem in practice mode. AI off. Draw the array [4, 5, 6, 7, 0, 1, 2] on paper. Mark the rotation point. Convince yourself by hand that comparing with nums[hi] works on every test you can imagine.
  3. Code the template. Run public tests. Then the dynamic private tests will throw the non-rotated case, the rotated-by-one case, the rotated-by-n-1 case, and arrays of length 1 and 2. A template that mis-handles hi = mid - 1 passes the medium cases and fails the boundary.
  4. If you fail, do not ask AI for the fix. Re-derive the predicate on paper first. Only then ask the assistant to Find Bugs. The integrity score deducts a few points for the hint; that small cost is the lesson on how rarely you actually need the agent.

The submission tag will record AI use. Six months from now, when an interviewer at Adyen or Stripe asks why your portfolio passed find-min without AI, you will have a clean answer.

In the AI-integrated workspace

Cursor, Copilot, and Claude Code will write find-min-in-rotated-sorted-array with one of two bugs about 30% of the time: comparing with nums[lo] (silent wrong answer on the non-rotated case), or using hi = mid - 1 (silent wrong answer when the minimum is at mid). Both bugs pass the LeetCode sample inputs because the sample is rotated; both fail on the dynamic test suite parikshan generates.

Verification ritual on every agent-generated rotated-sorted search:

  1. Ask: "what is the predicate, and is it monotone over indices?" The agent should be able to phrase it.
  2. Ask: "what does the function return on a non-rotated input?" If the agent has to think, the search direction is suspect.
  3. Trace by hand on [2, 1]. Length-2 rotation is where every wrong template dies.

This problem is the cleanest demonstration that a sorted array is not the precondition for binary search; a monotone predicate is. Engineers who internalise that distinction stop being intimidated by "the input is sorted, then mutated" specs. parikshan trains exactly that reframing.