Problem · LC 153

Find Minimum in Rotated Sorted Array

Medium
◧ Template B · pivot detection

How to recognize it

A sorted array that has been rotated at an unknown pivot, and you need the minimum (i.e. the rotation point). Signal words: "rotated sorted array", "no duplicates". The min is the single spot where order breaks.

The core idea

Compare nums[mid] to nums[hi] (the right end). If nums[mid] > nums[hi], the break — and therefore the minimum — is strictly to the right, so lo = mid+1. Otherwise the min is at mid or to its left, so hi = mid. Converge with lo < hi.

Why It's Tricky

The array is sorted in two pieces: [biggest...pivot] [smallest...bigish]. The minimum is the pivot. You can't just search for "the smallest value" with a simple loop because you don't know which half is which. The trick: always compare to the right end (not the left), because the right half's structure tells you where the break is.

The Key Insight

Compare nums[mid] to nums[hi], NOT to nums[lo]. If mid > hi, the minimum is RIGHT (the pivot is right). If mid ≤ hi, the minimum is AT MID or LEFT (mid is in the smaller piece). This comparison rule works because nums[hi] is always on the "small" side of the pivot.

Step-by-Step Walkthrough

Example: nums=[4,5,6,7,0,1,2], min is at index 4

lo=0, hi=6, mid=3 → nums[3]=7 > nums[6]=2 → pivot is RIGHT → lo=4
lo=4, hi=6, mid=5 → nums[5]=1 < nums[6]=2 → pivot is AT/LEFT → hi=5
lo=4, hi=5, mid=4 → nums[4]=0 < nums[5]=1 → pivot is AT/LEFT → hi=4
lo=4, hi=4 → DONE, return nums[4]=0

Why we never try left: If mid > hi, going left won't help — the left half is sorted and larger. The break is right.

time O(log n)
space O(1)
find_minimum_in_rotated_sorted_array
def findMin(nums):
    lo, hi = 0, len(nums) - 1
    while lo < hi:
        mid = (lo + hi) // 2
        if nums[mid] > nums[hi]:
            lo = mid + 1        # min is in the right, unsorted half
        else:
            hi = mid            # min is at mid or to its left
    return nums[lo]             # lo == hi == index of minimum

Interview gotchas

  • Compare against hi, not lo. Comparing to lo has an annoying edge case on a non-rotated array.
  • Use hi = mid (not mid-1) — mid could be the answer.
  • With duplicates (LC 154) add elif nums[mid]==nums[hi]: hi -= 1; worst case degrades to O(n).

💡 What to Say in the Interview

  • Say: "I'm looking for the pivot (minimum) in a rotated sorted array."
  • Explain: "I'll compare mid to the right end. If mid > right, the pivot is right. Otherwise, mid or left."
  • Key phrase: "Always compare to the right, not the left, because the right end is always on the 'small' side of the pivot."
  • Dry run: Show an example like [4,5,6,7,0,1,2] and trace through the comparisons.
  • Warn: "If there were duplicates, this breaks — we'd need to shrink hi by 1 when mid==hi."

↳Variants they'll pivot to

Solve the base problem, then interviewers escalate. These are the usual next steps — knowing the connection is worth more than memorizing each.