LC 153 · Medium · Template B · pivot detection

Find Minimum in Rotated Sorted Array

A sorted array that has been rotated, and you need the rotation point rather than a particular value.

Recognise it

Before any code, what in the question tells you this is the pattern?

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 brute force

Always have this one ready. It is the honest starting point, and it is what the real solution improves on.

Scan the array and keep the smallest value seen, or equivalently look for the single place where an element is smaller than the one before it.

O(n) time and O(1) space.

The array is still highly structured even after rotation, and a linear scan throws that structure away. There is exactly one point where the order breaks. Everything to its left is larger than everything to its right, and that is enough of a signal to steer a binary search.

The approach

The idea in plain language, before it becomes syntax.

Picture the rotated array as two sorted runs with one cliff between them. The minimum is the first element of the second run, which is exactly the bottom of the cliff. Your job is to locate that cliff without walking to it.

Compare the middle element against the last element rather than the first. If the middle is greater than the last, then the middle sits on the high run, the cliff has to be somewhere to its right, and you can safely move lo past mid. If the middle is less than the last, then the middle is already on the low run and could itself be the minimum, so you pull hi down to mid and keep it.

Comparing against the last element is what makes this work, and comparing against the first does not. In a fully sorted array that was never rotated, the middle is also less than the last, and the same branch quietly gives the right answer with no special case. Reaching for the first element instead forces you to detect rotation separately, which is more code and more ways to be wrong.

A rotated sorted array with a single cliff, comparing mid against the right end.One cliff. Everything left of it is bigger than everything right.40516273041526midhithe cliffa[mid] > a[hi] means the cliff is to the right, so lo = mid + 1a[mid] < a[hi] means mid could be the minimum, so hi = mid
Find Minimum in Rotated Sorted Array: the idea in one picture.edit source
Comparing to the right end works on an unrotated array too.12345midhinever rotated: a[mid] < a[hi], so hi = midThe same branch gives the right answer, with no special case for "not rotated".
Comparing against hi removes the need to detect rotation at all.

The algorithm

The same idea again, as steps you could follow with a pencil.

Flowchart comparing mid to the right boundary to locate the rotation point.lo = 0, hi = n - 1lo < hi ?yesa[mid] > a[hi] ?nohi = midyeslo = mid+1noa[lo] is minCompare against hi, never lo. Comparing to lo cannot tell a rotated array from a sorted one.
Find Minimum in Rotated Sorted Array: the loop, step by step.edit source
Time O(log n)Space O(1)

The solution

Now the code, and why each decision in it is the way it is.

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

There is no equality branch, because the array holds distinct values and the two inequalities already cover every case. Adding a third branch here tends to introduce bugs rather than remove them.

The loop runs while lo < hi and the answer is a[lo] when it ends. The range shrinks to one element, and the invariant says the minimum never left the range, so the last element standing is it.

If duplicates were allowed, the comparison against the last element could be a tie and neither half could be ruled out. The usual repair is to step hi down by one on a tie, which drops the guaranteed logarithmic bound to linear in the worst case. Worth saying out loud in an interview.

Where people slip

  • 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).

Your notes

What tripped you up here? Write it in your own words.

Where interviewers go next

Solve this one and the follow-up is usually a variation rather than a new idea. Knowing the connection is worth more than memorising each problem.

  • Find Min in Rotated II (dupes)LC 154When nums[mid] == nums[hi] you can't tell which side. Shrink hi by one. Worst case O(n), and interviewers ask WHY it degrades.
  • Find how many times rotatedvariantThe index of the minimum IS the rotation count. Same algorithm, return lo instead of nums[lo].