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)

The minimum of any array is one pass away.

class Solution:
    def findMin(self, 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 throws away the almost-sorted structure, and the problem explicitly requires O(log n) — this question exists to test whether you can binary-search without full sortedness.

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

The insight: 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, and if there is no drop the array is sorted and the first element wins.

class Solution:
    def findMin(self, 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 → return 0. ✓

Still O(n) time, O(1) space — but it identifies what we’re actually searching for (the drop), which sets up the binary search.

Approach 3 — Binary search against the right end

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

class Solution:
    def findMin(self, 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 survives partial disorder as long as one comparison still eliminates half the range. In rotated arrays the magic comparison is midpoint vs. endpoint: it reveals which half is clean-sorted and which half hides the anomaly (the rotation point), and you always recurse into the hiding half. Search for the structure, not for a value.