Skip to content
16-Week DSA Roadmap
LeetCode #153MediumProblem 8 of 8

Find Minimum in Rotated Sorted Array

A sorted array was cut in two and the halves swapped. Find its smallest number in O(log n) by binary searching for the cut.

  • Binary search on a rotated array
  • Compare with the right end

Before this, know: Binary search (lo, hi, mid), Sorted order

The problem in plain English

Start with a sorted array of different numbers, like [0, 1, 2, 4, 5, 6, 7]. Rotating it means taking some items off the front and sticking them on the back, in the same order. Rotate it 4 times and you get [4, 5, 6, 7, 0, 1, 2].

You’re given the rotated array (you don’t know how many times it was rotated) and must return its smallest number. Here, that’s 0.

Draw the numbers as bars and the shape is easy to see: a rising run, a sudden drop, and another rising run. We’ll call the drop the cliff. The minimum is always the first bar after the cliff.

40516273041526cliff
nums = [4, 5, 6, 7, 0, 1, 2]. Two rising runs with a cliff between them. The minimum (0, at index 4) is right after the cliff.

Rules that matter:

  • All numbers are different.
  • The array may have been rotated n times, which puts it back in sorted order: [11, 13, 15, 17]. Then there’s no cliff and the minimum is the first item.
  • You must run in O(log n) time, so reading every number isn’t allowed.

Before you code: think it through

Why compare nums[mid] with nums[hi] (the right end of the range)? Because inside one rising run, values only go up. So:

  • nums[mid] > nums[hi]: something bigger comes before something smaller. That can only happen if the cliff is between them. The minimum is to the right of mid.
  • nums[mid] < nums[hi]: from mid to hi everything rises with no cliff. Nothing right of mid is smaller than nums[mid]. The minimum is at mid or to its left.
40516273041526cliff↑mid↑hi
60710213244556cliff↑mid↑hi
Left: mid (7) is bigger than hi (2), so the cliff is to the right of mid. Right: mid (1) is smaller than hi (5), so mid..hi rises and the minimum is at mid or before it.

Pause and think

nums = [5, 6, 7, 1, 2, 3, 4], lo = 0, hi = 6, so mid = 3. nums[mid] = 1 and nums[hi] = 4. Which way do you go, and can you throw away mid itself?

Approach 1: Brute force

Look at every number and remember the smallest.

Brute force: look at every number

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

nums
  1. 40
  2. 51
  3. 62
  4. 73
  5. 04
  6. 15
  7. 26
variables
smallest
4
  • Looking at
  • Smallest so far
  • Already seen

4: smallest so far is still 4.

Step 1 / 8

Which line is running?

function findMin(nums) {  let smallest = nums[0];  for (const x of nums) {Running now:     if (x < smallest) smallest = x;  }  return smallest;}

Brute force: scan for the smallest

function findMin(nums) {  let smallest = nums[0];  for (const x of nums) {    if (x < smallest) smallest = x;  }  return smallest;}
def find_min(nums):    smallest = nums[0]    for x in nums:        if x < smallest:            smallest = x    return smallest

Why is it slow?

It reads all n numbers: 7 looks for 7 items, 5,000 looks for 5,000 items. That’s O(n). It’s correct, but the problem asks for O(log n), about 13 looks for 5,000 items, and the scan ignores that the array is almost sorted.

The pattern: binary search on a rotated array

A rotated sorted array isn’t sorted, but it’s sorted in two pieces, and one comparison with the right end tells you which piece mid is in. That’s enough to throw away half the range every round.

Pattern

Binary search on a rotated array

Template

Use it when: a sorted array has been rotated (shifted around) and you need its minimum, its rotation point, or a value, in O(log n).

Signal words

  • “rotated sorted array”
  • “rotated between 1 and n times”
  • “unique elements”
  • “O(log n)”
  • “find the minimum / pivot”

This is a different shape from the classic template. We’re not looking for a value we can test with ===; we’re narrowing down to one position (the minimum). That changes two things: the loop runs while lo < hi (stop when one candidate is left), and one side uses hi = mid (keep mid, it might be the answer).

Approach 2: Binary search for the cliff

  1. Set lo = 0 and hi = n − 1. The minimum is somewhere in nums[lo..hi].
  2. While lo < hi (more than one candidate):
  3. Compute mid = lo + (hi − lo) // 2.
  4. If nums[mid] > nums[hi]: the cliff is right of mid, and mid can’t be the minimum (something smaller sits after it). Set lo = mid + 1.
  5. Otherwise: the minimum is mid or something before it. Set hi = mid.
  6. When lo == hi, return nums[lo].

Press Play. The bars show the cliff as a dashed line. Each round, mid is compared with hi (amber), and the half without the cliff fades out. Try the not rotated edge case: nums[mid] is always smaller than nums[hi], so hi walks left until it reaches index 0.

Binary search for the cliff

nums = [3, 4, 5, 1, 2]

nums as heights: one rising run, a drop (the cliff), another rising run
3041521324cliff↑lo↑hi
variables
lo
0
mid
—
hi
4
nums[mid]
—
nums[hi]
2
decision
—
result
—
  • Minimum is in here (lo..hi)
  • mid
  • nums[hi], what we compare with
  • Ruled out
  • Minimum

The minimum is somewhere in nums[lo..hi], which starts as the whole array. We will shrink the range until only one index is left.

Step 1 / 6

Which line is running?

function findMin(nums) {  let lo = 0;Running now:   let hi = nums.length - 1; // the minimum is always inside nums[lo..hi]  while (lo < hi) {    const mid = lo + Math.floor((hi - lo) / 2);    if (nums[mid] > nums[hi]) {      lo = mid + 1; // the cliff is to the right of mid    } else {      hi = mid; // mid..hi is sorted, so mid might be the minimum: keep it    }  }  return nums[lo]; // lo === hi: one candidate left}

The code, line by line

Binary search for the cliff

function findMin(nums) {  let lo = 0;  let hi = nums.length - 1; // the minimum is always inside nums[lo..hi]  while (lo < hi) {    const mid = lo + Math.floor((hi - lo) / 2);    if (nums[mid] > nums[hi]) {      lo = mid + 1; // the cliff is to the right of mid    } else {      hi = mid; // mid..hi is sorted, so mid might be the minimum: keep it    }  }  return nums[lo]; // lo === hi: one candidate left}
def find_min(nums):    lo, hi = 0, len(nums) - 1  # the minimum is always inside nums[lo..hi]    while lo < hi:        mid = lo + (hi - lo) // 2        if nums[mid] > nums[hi]:            lo = mid + 1  # the cliff is to the right of mid        else:            hi = mid  # mid..hi is sorted, so mid might be the minimum: keep it    return nums[lo]  # lo == hi: one candidate left

JavaScript sets lo and hi on two lines and has closing braces, so its line numbers run ahead of Python’s; we give both.

  • Line 1: define the function. (LeetCode: var findMin = function(nums), or a method of class Solution in Python.)
  • Lines 2–3 (JS) / line 2 (Py): the minimum is somewhere in the whole array.
  • Line 4 (JS) / line 3 (Py): lo < hi, not <=. We stop when exactly one candidate is left, because that candidate must be the answer. With <= and hi = mid, the loop would never end once lo == hi.
  • Line 5 (JS) / line 4 (Py): the middle, rounded down. Because lo < hi, mid is always strictly less than hi, so we never compare a number with itself.
  • Lines 6–7 (JS) / 5–6 (Py): bigger than the right end means the cliff comes after mid. mid itself can’t be the minimum (the smaller nums[hi] exists), so skip it: lo = mid + 1.
  • Lines 8–9 (JS) / 7–8 (Py): otherwise mid..hi rises. The minimum is mid or to its left. Keep mid: hi = mid.
  • Line 12 (JS) / 9 (Py): lo == hi. One candidate left: the minimum.

Why compare with nums[hi] and not nums[lo]?

Comparing with the left end is ambiguous. In [1, 2, 3, 4, 5] (not rotated) and in [3, 4, 5, 1, 2] (rotated), nums[mid] > nums[lo] is true in both, but the minimum is on the left in the first and on the right in the second. Comparing with nums[hi] gives the right direction in every case.

Dry run

Trace nums = [4, 5, 6, 7, 0, 1, 2]. The minimum (0) is at index 4.

lohimidnums[mid]nums[hi]comparenext
063727 > 2: cliff is right of midlo = 4
465121 < 2: min at mid or lefthi = 5
454010 < 1: min at mid or lefthi = 4
44lo == hi: stopreturn nums[4] = 0
nums = [4, 5, 6, 7, 0, 1, 2]

The row where mid = 4 shows why we keep mid: nums[4] = 0 is the minimum, and hi = mid keeps it in the range. With hi = mid − 1 we’d have thrown away the answer.

Complexity

Scan every number

Time

O(n)

One look per number.

Space

O(1)

One variable for the smallest so far.

Binary search for the cliff

Time

O(log n)

Each round at least halves lo..hi. 5,000 numbers take about 13 rounds.

Space

O(1)

Just lo, hi and mid.

Common mistakes and edge cases

What to say out loud, in this order:

  1. “The array is two sorted runs with a cliff; the minimum is right after the cliff.”
  2. “Compare nums[mid] with nums[hi]: bigger means the cliff is to the right, smaller means mid..hi is sorted.”
  3. “I’m narrowing to one position, so while lo < hi, lo = mid + 1 on one side and hi = mid on the other.”
  4. Cost: O(log n) time, O(1) space.
  5. Dry-run the not-rotated case and a two-item case.

Likely follow-up questions:

  • “Return how many times it was rotated?” That’s the index of the minimum: return lo.
  • “What if there are duplicates?” (Problem 154.) When nums[mid] == nums[hi] you can’t tell which side the cliff is on, so shrink by one: hi -= 1. The worst case becomes O(n).
  • “Find a target value in the rotated array?” That’s Search in Rotated Sorted Array, in week 4.

Related problems: