Find Minimum in Rotated Sorted Array

MediumModified Binary SearchBlind 75MidOpen on LeetCodeUpdated Sep 21, 2026

You're given an array nums of distinct integers that was sorted in ascending order and then rotated between 1 and n times, where each rotation moves the last element to the front. So [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2], and n rotations give back the sorted array. Return the minimum value itself, not its index. Your solution must run in O(log n) time.

Examples

nums = [3,4,5,1,2] returns 1

The order drops from 5 to 1, and 1 is the minimum.

The values rise 3, 4, 5, drop to 1, then rise to 2. The drop marks where the original sorted array started, so the minimum is 1.

nums = [4,5,6,7,0,1,2] returns 0

This is [0,1,2,4,5,6,7] rotated 4 times. The value right after the drop from 7 is 0.

nums = [11,13,15,17] returns 11

Four rotations of a four-element array bring it back to sorted order. There is no drop, so the first value 11 is the minimum.

Constraints

1 <= nums.length <= 5000
All values unique.

Hints

Hint 1

The rotation point splits the array into two sorted runs, how can you home in on it?

Hint 2

A pointer toward the approach

Hint 3

The full approach, step by step

Drill This: Your Approach First

Answer, Then Reveal

In two or three sentences, how would you solve it and what's the complexity?

Skip to Reading

Approach

Shrink a range [lo, hi] that always contains the minimum. Compare the middle value with the right end: if nums[mid] > nums[hi], the drop to the minimum lies right of mid, so set lo = mid + 1; otherwise mid through hi is sorted and the minimum is at mid or left of it, so set hi = mid. When lo meets hi, nums[lo] is the minimum. O(log n) time, O(1) space.

Time

O(log n)

Space

O(1)

Pitfall

Comparing nums[mid] with nums[lo] instead of nums[hi]. On an unrotated array like [11,13,15,17] the left side always looks sorted and you move away from the minimum. Use hi = mid, not mid - 1, since mid may be the minimum.

Solutions

class Solution {
    public int findMin(int[] nums) {
        int lo = 0, hi = nums.length - 1;
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            if (nums[mid] > nums[hi]) lo = mid + 1;
            else hi = mid;
        }
        return nums[lo];
    }
}

class Solution:
    def findMin(self, nums) -> int:
        lo, hi = 0, len(nums) - 1
        while lo < hi:
            mid = (lo + hi) // 2
            if nums[mid] > nums[hi]:
                lo = mid + 1
            else:
                hi = mid
        return nums[lo]