Skip to main content
CodePeetCodePeet
CodePeet 250

Find Minimum in Rotated Sorted Array

MEDIUMProblemSolveExternal Links

Description

You are given a sorted array of distinct integers that has been rotated between 1 and n times. In a rotation, the last element of the array is moved to the front.

For example, if the original sorted array was [0, 1, 2, 4, 5, 6, 7], rotating it 4 times produces [4, 5, 6, 7, 0, 1, 2].

Given this rotated array, your task is to find and return the minimum element. You must design an algorithm that runs in O(log n) time.

Examples

Example 1

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

Output: 1

Explanation: The original sorted array was [1, 2, 3, 4, 5]. It was rotated 3 times, placing elements 3, 4, 5 at the front and 1, 2 at the back. The minimum element is 1.

Example 2

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

Output: 0

Explanation: The original sorted array was [0, 1, 2, 4, 5, 6, 7]. After rotating 4 times, it becomes [4, 5, 6, 7, 0, 1, 2]. The minimum element is 0.

Example 3

Input: nums = [11, 13, 15, 17]

Output: 11

Explanation: The array has been rotated 4 times (a full rotation), so it is back in its original sorted order. The minimum is simply the first element, 11.

Constraints

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

Editorial

Brute Force

Intuition

The simplest way to find the minimum is to ignore the sorted and rotated structure entirely and just scan every element. We walk through the array from start to end, keeping track of the smallest value we have seen so far.

Think of it like checking every book on a shelf to find the thinnest one. You pick up the first book, measure it, then compare each subsequent book against it. Whenever you find a thinner book, you update your record. By the time you reach the end of the shelf, you are holding the thinnest book.

This approach works correctly for any array, whether it is sorted, rotated, or completely random. However, it does not take advantage of the fact that the array has a special sorted-and-rotated structure.

Step-by-Step Explanation

Let's trace through with nums = [4, 5, 6, 7, 0, 1, 2]:

Step 1: Initialize min_val with the first element.

  • min_val = nums[0] = 4

Step 2: Check nums[1] = 5.

  • Is 5 < 4? No.
  • min_val remains 4.

Step 3: Check nums[2] = 6.

  • Is 6 < 4? No.
  • min_val remains 4.

Step 4: Check nums[3] = 7.

  • Is 7 < 4? No.
  • min_val remains 4.

Step 5: Check nums[4] = 0.

  • Is 0 < 4? YES!
  • Update min_val = 0. We just crossed the rotation point.

Step 6: Check nums[5] = 1.

  • Is 1 < 0? No.
  • min_val remains 0.

Step 7: Check nums[6] = 2.

  • Is 2 < 0? No.
  • min_val remains 0.

Result: Return min_val = 0.

Linear Scan — Checking Every Element — Watch how we scan each element left to right, updating min_val only when we encounter a smaller value at the rotation point.

Algorithm

  1. Initialize min_val = nums[0]
  2. For each element nums[i] from index 1 to n-1:
    • If nums[i] < min_val, update min_val = nums[i]
  3. Return min_val

Code

class Solution {
public:
    int findMin(vector<int>& nums) {
        int minVal = nums[0];
        for (int i = 1; i < nums.size(); i++) {
            minVal = min(minVal, nums[i]);
        }
        return minVal;
    }
};
class Solution:
    def findMin(self, nums: list[int]) -> int:
        min_val = nums[0]
        for i in range(1, len(nums)):
            min_val = min(min_val, nums[i])
        return min_val
class Solution {
    public int findMin(int[] nums) {
        int minVal = nums[0];
        for (int i = 1; i < nums.length; i++) {
            minVal = Math.min(minVal, nums[i]);
        }
        return minVal;
    }
}

Complexity Analysis

Time Complexity: O(n)

We visit every element in the array exactly once. Each comparison is a constant-time operation, so the total time is proportional to the array length n.

Space Complexity: O(1)

We only use a single variable min_val to track the minimum. No additional data structures are needed, so space usage is constant regardless of input size.

Why This Approach Is Not Efficient

The brute force approach scans every element, taking O(n) time. But the problem explicitly asks for O(log n) time, and we are not using the crucial property: the array is sorted and rotated.

A sorted-and-rotated array is not random — it consists of two sorted halves. The minimum sits exactly at the boundary where the two halves meet (the rotation point). If we can figure out which half contains the rotation point, we can discard the other half entirely.

This is the classic setup for binary search: at every step, we can eliminate roughly half the remaining elements. Instead of checking all n elements, we only need about log₂(n) steps. For n = 5000, that is roughly 13 comparisons instead of 5000.

Bar chart comparing O(n) linear scan versus O(log n) binary search for n=5000
Bar chart comparing O(n) linear scan versus O(log n) binary search for n=5000

Optimal Approach - Binary Search

Intuition

A rotated sorted array has a distinctive shape: it climbs upward, then suddenly drops at the rotation point, and climbs upward again. The minimum element sits right at that drop.

The array can be split into two sorted segments:

  • The left segment contains elements that were moved from the end of the original sorted array (these are the larger values).
  • The right segment contains elements that were at the beginning of the original sorted array (these are the smaller values, including the minimum).

The key insight for binary search is: we compare the middle element with the rightmost element.

  • If nums[mid] > nums[high], the rotation point (and the minimum) must be somewhere to the right of mid. The left half including mid is part of the higher sorted segment. So we set low = mid + 1.
  • If nums[mid] <= nums[high], the right half from mid to high is properly sorted, meaning the minimum is either at mid or to the left of mid. So we set high = mid.

We also use an early termination check: if nums[low] < nums[high], the current subarray is already sorted with no rotation, so the minimum is simply nums[low].

This binary search converges when low == high, and nums[low] is the answer.

Diagram showing a rotated sorted array with two ascending segments and the minimum at the inflection point
Diagram showing a rotated sorted array with two ascending segments and the minimum at the inflection point

Step-by-Step Explanation

Let's trace through with nums = [4, 5, 6, 7, 0, 1, 2]:

Step 1: Initialize low = 0, high = 6.

  • Current search space: [4, 5, 6, 7, 0, 1, 2]

Step 2: Check if already sorted: nums[0] = 4, nums[6] = 2. Is 4 < 2? No, so the array is rotated.

Step 3: Calculate mid = (0 + 6) / 2 = 3. nums[mid] = nums[3] = 7.

  • Compare nums[mid] = 7 with nums[high] = nums[6] = 2.
  • Is 7 > 2? YES. The minimum must be in the right half (mid is in the left sorted segment).
  • Set low = mid + 1 = 4.

Step 4: New search space: indices [4, 5, 6] → values [0, 1, 2].

  • Check if sorted: nums[4] = 0, nums[6] = 2. Is 0 < 2? YES! The subarray is sorted.
  • Return nums[low] = nums[4] = 0.

Result: Minimum is 0. Found in just 2 iterations instead of scanning all 7 elements.

Binary Search — Halving the Search Space — Watch how binary search eliminates half the array at each step by comparing the middle element with the rightmost element to determine which half contains the minimum.

Algorithm

  1. Initialize low = 0, high = n - 1
  2. While low < high:
    a. If nums[low] < nums[high], the subarray is sorted — return nums[low]
    b. Calculate mid = (low + high) / 2
    c. If nums[mid] > nums[high], the minimum is in the right half — set low = mid + 1
    d. Else, the minimum is at mid or in the left half — set high = mid
  3. Return nums[low]

Code

class Solution {
public:
    int findMin(vector<int>& nums) {
        int lo = 0, hi = nums.size() - 1;
        
        while (lo < hi) {
            // If current subarray is already sorted
            if (nums[lo] < nums[hi]) {
                return nums[lo];
            }
            
            int mid = lo + (hi - lo) / 2;
            
            if (nums[mid] > nums[hi]) {
                // Min is in the right half
                lo = mid + 1;
            } else {
                // Min is at mid or in the left half
                hi = mid;
            }
        }
        
        return nums[lo];
    }
};
class Solution:
    def findMin(self, nums: list[int]) -> int:
        lo, hi = 0, len(nums) - 1
        
        while lo < hi:
            # If current subarray is already sorted
            if nums[lo] < nums[hi]:
                return nums[lo]
            
            mid = (lo + hi) // 2
            
            if nums[mid] > nums[hi]:
                # Min is in the right half
                lo = mid + 1
            else:
                # Min is at mid or in the left half
                hi = mid
        
        return nums[lo]
class Solution {
    public int findMin(int[] nums) {
        int lo = 0, hi = nums.length - 1;
        
        while (lo < hi) {
            // If current subarray is already sorted
            if (nums[lo] < nums[hi]) {
                return nums[lo];
            }
            
            int mid = lo + (hi - lo) / 2;
            
            if (nums[mid] > nums[hi]) {
                // Min is in the right half
                lo = mid + 1;
            } else {
                // Min is at mid or in the left half
                hi = mid;
            }
        }
        
        return nums[lo];
    }
}

Complexity Analysis

Time Complexity: O(log n)

At each iteration of the while loop, we cut the search space roughly in half by moving either low or high to the midpoint. Starting with n elements, we need at most log₂(n) iterations to narrow down to a single element. For n = 5000, this means about 13 comparisons.

Space Complexity: O(1)

We only use a constant number of variables (lo, hi, mid) regardless of the input size. No recursion or auxiliary data structures are used.