Find Minimum in Rotated Sorted Array

Problem Description

A sorted array of unique integers was rotated at some unknown pivot. Find the minimum element.

You must run in O(log n) time.

Examples

Constraints

• n == nums.length
• 1 ≤ n ≤ 5000
• -5000 ≤ nums[i] ≤ 5000
• All integers are unique.
• nums is sorted and rotated between 1 and n times.

The Minimum Is at the Boundary Between the Two Sorted Halves

Rotating a sorted array creates two sorted halves joined at a break point. The minimum is always the first element of the right half (the smaller half). Binary search finds this break point by checking one condition: if nums[mid] > nums[right], the middle element belongs to the left (larger) half, so the break point is somewhere to the right. Otherwise, mid is in the right (smaller) half, and the minimum is at or before mid.

Solution 1: Linear Scan

Walk through the array and return the first time the current element is less than the previous one.

class Solution {
    public int findMin(int[] nums) {
        int min = nums[0];
        for (int num : nums) min = Math.min(min, num);
        return min;
    }
}

class Solution:
    def findMin(self, nums: list[int]) -> int:
        return min(nums)

#include <vector>
#include <algorithm>

class Solution {
public:
    int findMin(std::vector<int>& nums) {
        return *std::min_element(nums.begin(), nums.end());
    }
};

Complexity Analysis:

• Time Complexity: O(n). Full scan.
• Space Complexity: O(1).

Where it breaks: doesn’t meet the O(log n) requirement. It also ignores the sorted structure entirely, which an interviewer will flag.

Solution 2: Binary Search

Eliminate the sorted half at each step. If nums[mid] > nums[right], the right half (including mid) is the larger sorted portion, so the minimum is to the right: left = mid + 1. Otherwise, the minimum is at mid or to its left: right = mid.

class Solution {
    public int findMin(int[] nums) {
        int left = 0, right = nums.length - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] > nums[right]) {
                // mid is in the left (larger) half; minimum is to the right
                left = mid + 1;
            } else {
                // mid might be the minimum, or the minimum is to its left
                right = mid;
            }
        }
        return nums[left];
    }
}

class Solution:
    def findMin(self, nums: list[int]) -> int:
        left, right = 0, len(nums) - 1
        while left < right:
            mid = (left + right) // 2
            if nums[mid] > nums[right]:
                # mid is in the left (larger) half; minimum is to the right
                left = mid + 1
            else:
                # mid might be the minimum, or the minimum is to its left
                right = mid
        return nums[left]

#include <vector>

class Solution {
public:
    int findMin(std::vector<int>& nums) {
        int left = 0, right = nums.size() - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] > nums[right]) {
                // mid is in the left (larger) half; minimum is to the right
                left = mid + 1;
            } else {
                // mid might be the minimum, or the minimum is to its left
                right = mid;
            }
        }
        return nums[left];
    }
};

Complexity Analysis:

• Time Complexity: O(log n). The search space halves every iteration.
• Space Complexity: O(1). Two pointer variables.

Where it breaks: this solution assumes all values are unique. If duplicates are allowed (LeetCode 154), nums[mid] == nums[right] becomes possible and you can’t determine which half the minimum is in, requiring right-- as a fallback. Worst case becomes O(n) for that variant.

Why Compare Against nums[right] and Not nums[left]?

Comparing nums[mid] to nums[left] would tell you whether mid is in the left sorted half, but it introduces ambiguity when the array has no rotation (no break point). Comparing to nums[right] works cleanly because the minimum is always in the relationship with the right boundary: if mid is larger than right, the rotation point is between mid and right.

Common Mistakes

• Using right = mid - 1 instead of right = mid. The minimum could be at mid itself. Setting right = mid - 1 skips it.
• Comparing nums[mid] against nums[left] instead of nums[right]. The left-comparison approach needs an extra case for the no-rotation scenario and is harder to get right.
• Forgetting to handle the no-rotation case. When the array is not rotated, nums[mid] <= nums[right] for every mid, and right shrinks correctly to left = 0. No special casing needed.

Frequently Asked Questions

What if the array has only one element? left == right immediately, so the while loop doesn’t execute. You return nums[0]. Correct.

Does this work if the array is rotated n times (i.e., not rotated at all)? Yes. A fully sorted array satisfies nums[mid] <= nums[right] at every step, so right shrinks to 0 and you return the first element, which is the minimum.

How does this extend to arrays with duplicates? When nums[mid] == nums[right], you can’t determine which half the minimum is in. The safe fallback is right--, which reduces the search space by one without losing the minimum. Worst case degrades to O(n) for all-duplicate arrays.

← All Problems