LeetCode 153 - Find Minimum in Rotated Sorted Array

2026-07-06

medium　array　binary search

If you're not familiar with binary search, check out LeetCode 704 - Binary Search first.

You are given an array of length n which was originally sorted in ascending order. It has been rotated between 1 and n times.

For example, [1,2,3,4,5,6] might become:

• [3,4,5,6,1,2] if rotated 4 times.
• [1,2,3,4,5,6] if rotated 6 times (back to original).

All elements are unique. Return the minimum element of the array.

A linear O(N) solution is trivial — can you do it in O(log N)?

Example 1:

Input: nums = [3,4,5,6,1,2]

Output: 1

Example 2:

Input: nums = [4,5,0,1,2,3]

Output: 0

Example 3:

Input: nums = [4,5,6,7]

Output: 4

Constraints:

• 1 <= nums.length <= 1,000
• -1,000 <= nums[i] <= 1,000
• All integers in nums are unique.

Solution 1:

class Solution:
    def findMin(self, nums: List[int]) -> int:
        # Approach: Binary Search with Running Minimum
        # 1. Seed the minimum with nums[0], start the search from index 1.
        # 2. At each midpoint, if nums[mid] < current minimum, update the minimum
        #    and search the left half for something even smaller.
        # 3. Otherwise, the minimum must lie in the right half — move left pointer right.
        # 4. When pointers cross, return the tracked minimum.
        # Time Complexity: O(log N).
        # Space Complexity: O(1).
        min_num = nums[0]
        l_idx, r_idx = 1, len(nums) - 1
        while l_idx <= r_idx:
            mid_idx = (l_idx + r_idx) // 2
            if nums[mid_idx] < min_num:
                min_num = nums[mid_idx]
                r_idx = mid_idx - 1
            else:
                l_idx = mid_idx + 1
        return min_num

Solution 2:

class Solution:
    def findMin(self, nums: List[int]) -> int:
        # Approach: Binary Search anchored on the right boundary
        # Key insight: compare nums[mid] against nums[right].
        # - If nums[mid] > nums[right], the rotation point (and the minimum) must be
        #   in the right half — move left pointer to mid + 1.
        # - If nums[mid] <= nums[right], the minimum is at mid or to its left —
        #   move right pointer to mid (not mid - 1, to avoid skipping the answer).
        # Loop condition is l < r (not <=), so when they meet, that index is the answer.
        # Time Complexity: O(log N).
        # Space Complexity: O(1).
        l_idx, r_idx = 0, len(nums) - 1
        while l_idx < r_idx:
            mid_idx = (l_idx + r_idx) // 2
            if nums[mid_idx] > nums[r_idx]:
                l_idx = mid_idx + 1
            else:
                r_idx = mid_idx
        return nums[l_idx]

Conclusion

Today we found the minimum in a rotated sorted array two ways.

Solution 1 tracks a running minimum. It seeds min_num with nums[0], then binary searches the rest. When a smaller value is found at the midpoint, it updates the minimum and searches left for something even smaller; otherwise it goes right. Correct, but the logic is a bit indirect — the running variable adds a layer of bookkeeping.

Solution 2 is cleaner. The core insight: compare nums[mid] against nums[right]. If mid is larger than right, the array must have "wrapped" somewhere between mid and right — the minimum is in that right half. If mid is smaller or equal to right, the right portion is already sorted and the minimum is at mid or to its left.

Two subtle details in Solution 2: the loop uses l < r instead of l <= r (so it exits as soon as both pointers converge on the answer), and the right pointer is set to mid rather than mid - 1 (so the current midpoint is never prematurely discarded as a candidate).