Find Minimum in Rotated Sorted Array (LeetCode 153)

The problem

A sorted array of distinct integers has been rotated some number of times, so [0, 1, 2, 4, 5, 6, 7] might now be [4, 5, 6, 7, 0, 1, 2]. Return the minimum element, in O(log n) time.

Input:  [3, 4, 5, 1, 2]
Output: 1

The original array was [1, 2, 3, 4, 5], rotated three times. The minimum 1 sits right after the “drop” from 5 to 1.

How to think about it

Start with brute force. min(nums) is one line and O(n). It works, but the problem explicitly asks for O(log n), so the interviewer wants you to use the sorted structure.

Picture the array as two rising runs. A rotated sorted array is a high run followed by a low run: [3, 4, 5] then [1, 2]. The minimum is the first element of the low run. Every element of the high run is greater than every element of the low run, and in particular greater than the last element nums[hi].

The key insight: compare nums[mid] with nums[hi]. If nums[mid] > nums[hi], then mid is in the high run, so the minimum is strictly to the right: lo = mid + 1. Otherwise nums[mid] <= nums[hi], so mid is in the low run (or the array isn’t rotated), and the minimum is at mid or to its left: hi = mid. This is a “first true” boundary search for the first element that is <= the last element.

Why not compare with nums[lo]? If the array isn’t rotated, nums[lo] < nums[mid] and you can’t tell whether to go left or right without a special case. Comparing with hi handles both cases with one rule.

Which pattern is this? Binary search for a boundary in a rotated array. The tell is “rotated sorted” plus “minimum” or “pivot”. Use the lo < hi, hi = mid template.

Approach

1. Set lo = 0, hi = len(nums) - 1.
2. While lo < hi:
   • mid = (lo + hi) // 2.
   • If nums[mid] > nums[hi], set lo = mid + 1.
   • Else set hi = mid.
3. Return nums[lo].

Solution

def find_min_rotated(nums):
    lo, hi = 0, len(nums) - 1
    while lo < hi:
        mid = (lo + hi) // 2
        if nums[mid] > nums[hi]: lo = mid + 1   # mid is in the high run: drop is to the right
        else: hi = mid                          # mid is in the low run: min is mid or left
    return nums[lo]
# find_min_rotated([3,4,5,1,2]) -> 1

Dry run

On [3, 4, 5, 1, 2]:

Now lo == hi == 3, and nums[3] is 1.

Complexity

• Time: O(log n). The range halves every step.
• Space: O(1).

Edge cases and pitfalls

• Not rotated (or rotated n times), like [1, 2, 3]: nums[mid] <= nums[hi] every time, so hi slides down to index 0.
• Single element returns it immediately.
• Two elements like [2, 1]: mid = 0, 2 > 1, so lo = 1 and the answer is 1.
• hi = mid - 1 is a bug here: mid itself may be the minimum.
• Duplicates (LeetCode 154) break the rule when nums[mid] == nums[hi]. The fix is hi -= 1 in that case, which makes the worst case O(n).

Related problems

• Search in Rotated Sorted Array (LeetCode 33): search for a target in the same kind of array.
• First Bad Version (LeetCode 278): the same “first true” boundary template.
• Find Peak Element (LeetCode 162): compare mid with a neighbour to decide which half to keep.