Find Minimum in Rotated Sorted Array

medium
Binary SearchArrayBinary Search

Given a sorted array of unique integers nums that has been rotated between 1 and n times, find the minimum element. An array sorted in ascending order is rotated by shifting elements from the beginning to the end.

For example, the array [0,1,2,4,5,6,7] might be rotated to [4,5,6,7,0,1,2]. You must write an algorithm that runs in O(log n) time.

Examples

Example 1

  • Input: nums = [3,4,5,1,2]
  • Output: 1
  • Explanation: The original array was [1,2,3,4,5] rotated 3 times.

Example 2

  • Input: nums = [4,5,6,7,0,1,2]
  • Output: 0
  • Explanation: The original array was [0,1,2,4,5,6,7] rotated 4 times.

Example 3

  • Input: nums = [11,13,15,17]
  • Output: 11
  • Explanation: The array was not rotated (or rotated n times), so the minimum is the first element.

Constraints

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

Approaches

2 worked solutions ranked from straightforward to optimal — each with intuition, algorithm, complexity, and verified code in C++, Java, Python, and Go.

Approach 1

Linear Scan

Intuition

The simplest approach is to iterate through the entire array and track the minimum value. While this does not leverage the sorted-and-rotated property and runs in linear time, it always finds the correct answer. In a rotated sorted array the minimum is the element where the ascending order breaks, so we can also find it by looking for the first element smaller than its predecessor.

Algorithm

  1. Initialize the minimum value as the first element.
  2. Iterate through the array from index 1 to n - 1.
  3. If the current element is smaller than the minimum, update the minimum.
  4. Alternatively, if nums[i] < nums[i - 1], the current element is the minimum and we can return immediately.
  5. Return the minimum value.
TimeO(n)SpaceO(1)

Code (C++ · Java · Python · Go)

C++17
class Solution {
public:
    int findMin(vector<int>& nums) {
        int minVal = nums[0];
        for (int i = 1; i < nums.size(); i++) {
            if (nums[i] < minVal) {
                return nums[i];
            }
        }
        return minVal;
    }
};
Java 21
class Solution {
    public int findMin(int[] nums) {
        int minVal = nums[0];
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] < minVal) {
                return nums[i];
            }
        }
        return minVal;
    }
}
Python 3.12
def findMin(nums: list[int]) -> int:
    min_val = nums[0]
    for i in range(1, len(nums)):
        if nums[i] < min_val:
            return nums[i]
    return min_val
Go 1.26
func findMin(nums []int) int {
    minVal := nums[0]
    for i := 1; i < len(nums); i++ {
        if nums[i] < minVal {
            return nums[i]
        }
    }
    return minVal
}
Approach 2

Binary Search

Intuition

A rotated sorted array has two sorted halves. The minimum element is the pivot point where the rotation happened. We can use binary search to find it in O(log n) time. The key observation is: if the middle element is greater than the rightmost element, the minimum must be in the right half (the rotation point is there). Otherwise, the minimum is in the left half including mid. We keep narrowing the search space until left equals right.

Algorithm

  1. Initialize left = 0 and right = n - 1.
  2. While left < right, compute mid = left + (right - left) / 2.
  3. If nums[mid] > nums[right], the minimum is in the right half, so set left = mid + 1.
  4. Otherwise, the minimum is at mid or in the left half, so set right = mid.
  5. When the loop ends, left == right and points to the minimum element.
TimeO(log n)SpaceO(1)

Code (C++ · Java · Python · Go)

C++17
class Solution {
public:
    int findMin(vector<int>& nums) {
        int left = 0, right = nums.size() - 1;

        while (left < right) {
            int mid = left + (right - left) / 2;

            if (nums[mid] > nums[right]) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }

        return nums[left];
    }
};
Java 21
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]) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }

        return nums[left];
    }
}
Python 3.12
def findMin(nums: list[int]) -> int:
    left, right = 0, len(nums) - 1

    while left < right:
        mid = left + (right - left) // 2

        if nums[mid] > nums[right]:
            left = mid + 1
        else:
            right = mid

    return nums[left]
Go 1.26
func findMin(nums []int) int {
    left, right := 0, len(nums)-1

    for left < right {
        mid := left + (right-left)/2

        if nums[mid] > nums[right] {
            left = mid + 1
        } else {
            right = mid
        }
    }

    return nums[left]
}

Frequently asked questions

What is the optimal time complexity of Find Minimum in Rotated Sorted Array?

The most efficient approach in this guide ("Binary Search") runs in O(log n) time and uses O(1) extra space. Earlier brute-force approaches are slower; see all 2 approaches above for the full progression.

What pattern does Find Minimum in Rotated Sorted Array use?

Find Minimum in Rotated Sorted Array is a medium-level Binary Search problem involving Array, Binary Search. Recognizing the pattern is half the work — see the intuition section above for how to spot it.

Can Find Minimum in Rotated Sorted Array be solved without extra space?

The most space-efficient approach in this guide uses O(1) extra space (excluding the input). If you're aiming for in-place — see the trade-off in the algorithm section above — the brute-force approach uses O(1), while the optimized version uses O(1).

Which programming languages does this Ratta solution support?

Every approach above ships with verified, runnable solutions in C++, Java, Python, and Go. The starter templates in the workspace match the same four languages so you can practice in your interview language of choice.

Original problem: leetcode.com

Loading editor...
Input
nums=
[3,4,5,1,2]
Expected Output
1