Find Minimum in Rotated Sorted Array

Problem

An array of distinct integers was sorted in ascending order, then rotated some number of times between 1 and n: rotating once moves the last element to the front. For example, [0, 1, 2, 4, 5, 6, 7] rotated 4 times becomes [4, 5, 6, 7, 0, 1, 2] (rotating n times gives back the original).

Given the rotated array nums, return its minimum element in O(log n) time.

Examples

• Input: nums = [3, 4, 5, 1, 2] → Output: 1 (Original [1, 2, 3, 4, 5] rotated 3 times; the minimum is 1.)
• Input: nums = [4, 5, 6, 7, 0, 1, 2] → Output: 0 (The “drop” from 7 to 0 marks where the minimum sits.)
• Input: nums = [11, 13, 15, 17] → Output: 11 (Rotated n times — the array is fully sorted, so the first element is the minimum.)

Constraints

• 1 <= nums.length <= 5000
• -5000 <= nums[i] <= 5000
• All elements are unique.
• The array was sorted, then rotated between 1 and n times.
• Required time complexity: O(log n).

Think about it first

TL;DR

Binary search comparing nums[mid] against nums[hi] to pick the half containing the rotation point — O(log n) time, O(1) space.

Approach 1 — Brute force (scan for the minimum)

Scan every element and keep the smallest.

def findMin(nums: list[int]) -> int:
    best = nums[0]
    for x in nums:
        if x < best:
            best = x
    return best

(Equivalently min(nums).) Time O(n), space O(1). It passes at n <= 5000, but it ignores the array’s near-sorted structure, and the problem requires O(log n).

Approach 2 — Find the drop (linear, structure-aware)

A rotated sorted array with distinct values is ascending everywhere except at most one place: the “drop” where the largest element is followed by the smallest. Scan for the single index where nums[i] > nums[i + 1]; the minimum is right after it. If there is no drop, the array is sorted and the first element is the minimum.

def findMin(nums: list[int]) -> int:
    for i in range(len(nums) - 1):
        if nums[i] > nums[i + 1]:
            return nums[i + 1]
    return nums[0]

Walkthrough on [4, 5, 6, 7, 0, 1, 2]: pairs (4,5), (5,6), (6,7) ascend; (7,0) drops, so return 0.

Still O(n) time, O(1) space, but it names what we are searching for (the drop), which sets up the binary search.

Approach 3 — Binary search against the right end

Comparing nums[mid] to nums[hi] tells you which side of the drop mid is on. If nums[mid] > nums[hi], the range from mid to hi is not sorted, so the drop (and the minimum) lies strictly to the right of mid. If nums[mid] < nums[hi], the range from mid to hi is sorted, so the minimum is at mid or to its left. Either way, half the range is eliminated per comparison: the search is driven by a structural condition rather than a target value. (Distinct elements guarantee nums[mid] != nums[hi] while lo < hi.)

def findMin(nums: list[int]) -> int:
    lo, hi = 0, len(nums) - 1
    while lo < hi:
        mid = (lo + hi) // 2
        if nums[mid] > nums[hi]:
            lo = mid + 1      # drop is right of mid
        else:
            hi = mid          # mid could be the minimum
    return nums[lo]

Walkthrough on nums = [3, 4, 5, 1, 2]:

1. lo=0, hi=4 → mid=2, nums[2]=5 > nums[4]=2 → lo=3.
2. lo=3, hi=4 → mid=3, nums[3]=1 < nums[4]=2 → hi=3.
3. lo == hi == 3 → return nums[3] = 1.

And on the fully-sorted [11, 13, 15, 17]: mid=1, 13 < 17 → hi=1; mid=0, 11 < 13 → hi=0; return nums[0] = 11.

Time O(log n), space O(1).

Common pitfalls

• Comparing nums[mid] with nums[lo] instead of nums[hi] — with the left end the comparison is ambiguous (a sorted prefix doesn’t tell you where the drop is), and the already-sorted case breaks. Anchor to the right end.
• Using hi = mid - 1 when nums[mid] <= nums[hi] — mid itself may be the minimum, and stepping past it loses the answer. This search needs the lo < hi / hi = mid convention.
• Comparing against a fixed nums[-1] value works here, but the same habit breaks on the follow-up with duplicates (LeetCode 154), where equal values force an hi -= 1 shrink.
• Assuming the array is always “really” rotated: rotating n times yields a fully sorted array, and code that unconditionally looks for a drop must still return nums[0] in that case.

Pattern takeaway

Binary search works on partial disorder as long as one comparison still eliminates half the range. In a rotated array, the comparison is midpoint versus endpoint: it identifies which half is sorted and which half contains the rotation point, and you always keep searching the half that contains it. Search on the structure, not on a specific value.