Find Minimum in Rotated Sorted Array

Problem Statement

An array of distinct integers was sorted in increasing order and then rotated: some number of elements were moved, in order, from the front to the back. For example, [1, 3, 6, 9, 12] rotated by three positions becomes [9, 12, 1, 3, 6]. Rotating by the array’s length gives back the original sorted array.

Given the rotated array nums, return its smallest element. Your algorithm must run in O(log n) time.

Examples

Example 1:

Input: nums = [6,9,12,1,3]
Output: 1
Explanation: The original array was [1,3,6,9,12], rotated so that 6 comes first.

Example 2:

Input: nums = [40,10,20,30]
Output: 10
Explanation: Only the largest value was moved to the front, so the minimum is at index 1.

Example 3:

Input: nums = [-4,0,5,8]
Output: -4
Explanation: The array is fully sorted (it was rotated by its own length), so the first element is the minimum.

Constraints

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

Approach 1: Linear Scan for the Drop

Algorithm

In a rotated sorted array, values increase everywhere except at one spot: the point where the largest value is followed by the smallest. If there is no such drop, the array is fully sorted and the first element is the minimum.

1. Walk the array from index 1.
2. The first time nums[i] < nums[i - 1], return nums[i].
3. If no drop is found, return nums[0].

This is correct and easy to explain, but it is O(n) and does not meet the O(log n) requirement.

Implementation

Python:

from typing import List


class Solution:
    def findMin(self, nums: List[int]) -> int:
        # The minimum is the only element smaller than its left neighbor
        for i in range(1, len(nums)):
            if nums[i] < nums[i - 1]:
                return nums[i]
        # No drop: the array is not rotated
        return nums[0]

Java:

class Solution {
    public int findMin(int[] nums) {
        // The minimum is the only element smaller than its left neighbor
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] < nums[i - 1]) {
                return nums[i];
            }
        }
        // No drop: the array is not rotated
        return nums[0];
    }
}

Go:

func findMin(nums []int) int {
    // The minimum is the only element smaller than its left neighbor
    for i := 1; i < len(nums); i++ {
        if nums[i] < nums[i-1] {
            return nums[i]
        }
    }
    // No drop: the array is not rotated
    return nums[0]
}

JavaScript:

/**
 * @param {number[]} nums
 * @return {number}
 */
var findMin = function(nums) {
    // The minimum is the only element smaller than its left neighbor
    for (let i = 1; i < nums.length; i++) {
        if (nums[i] < nums[i - 1]) {
            return nums[i];
        }
    }
    // No drop: the array is not rotated
    return nums[0];
};

C#:

public class Solution {
    public int FindMin(int[] nums) {
        // The minimum is the only element smaller than its left neighbor
        for (int i = 1; i < nums.Length; i++) {
            if (nums[i] < nums[i - 1]) {
                return nums[i];
            }
        }
        // No drop: the array is not rotated
        return nums[0];
    }
}

C++:

#include <vector>
using namespace std;

class Solution {
public:
    int findMin(vector<int>& nums) {
        // The minimum is the only element smaller than its left neighbor
        for (size_t i = 1; i < nums.size(); i++) {
            if (nums[i] < nums[i - 1]) {
                return nums[i];
            }
        }
        // No drop: the array is not rotated
        return nums[0];
    }
};

Complexity Analysis

• Time: O(n) in the worst case, when the drop is near the end or the array is not rotated.
• Space: O(1).

Approach 2: Binary Search Against the Right End (Optimal)

Algorithm

Picture the rotated array as two sorted runs: a left run of larger values and a right run of smaller values, with the minimum at the start of the right run. Every value in the left run is greater than every value in the right run, including the last element nums[hi].

So comparing nums[mid] with nums[hi] tells us which run mid is in:

• If nums[mid] > nums[hi], mid is in the left run. The minimum is strictly to the right: lo = mid + 1.
• Otherwise nums[mid] < nums[hi] (values are distinct), so mid is in the right run. The minimum is at mid or to its left: hi = mid.

Steps:

1. Set lo = 0, hi = n - 1.
2. While lo < hi, compute mid = lo + (hi - lo) / 2 and shrink the range using the rule above.
3. When lo == hi, that index holds the minimum.

The loop keeps the minimum inside [lo, hi] at every step, and the range shrinks every iteration because mid < hi.

Implementation

Python:

from typing import List


class Solution:
    def findMin(self, nums: List[int]) -> int:
        lo, hi = 0, len(nums) - 1
        while lo < hi:
            mid = (lo + hi) // 2
            if nums[mid] > nums[hi]:
                lo = mid + 1  # mid is in the larger left run
            else:
                hi = mid      # mid is in the smaller right run, maybe the minimum
        return nums[lo]

Java:

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; // mid is in the larger left run
            } else {
                hi = mid;     // mid is in the smaller right run, maybe the minimum
            }
        }
        return nums[lo];
    }
}

Go:

func findMin(nums []int) int {
    lo, hi := 0, len(nums)-1
    for lo < hi {
        mid := lo + (hi-lo)/2
        if nums[mid] > nums[hi] {
            lo = mid + 1 // mid is in the larger left run
        } else {
            hi = mid // mid is in the smaller right run, maybe the minimum
        }
    }
    return nums[lo]
}

JavaScript:

/**
 * @param {number[]} nums
 * @return {number}
 */
var findMin = function(nums) {
    let lo = 0;
    let hi = nums.length - 1;
    while (lo < hi) {
        const mid = lo + ((hi - lo) >> 1);
        if (nums[mid] > nums[hi]) {
            lo = mid + 1; // mid is in the larger left run
        } else {
            hi = mid;     // mid is in the smaller right run, maybe the minimum
        }
    }
    return nums[lo];
};

C#:

public 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; // mid is in the larger left run
            } else {
                hi = mid;     // mid is in the smaller right run, maybe the minimum
            }
        }
        return nums[lo];
    }
}

C++:

#include <vector>
using namespace std;

class Solution {
public:
    int findMin(vector<int>& nums) {
        int lo = 0, hi = static_cast<int>(nums.size()) - 1;
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            if (nums[mid] > nums[hi]) {
                lo = mid + 1; // mid is in the larger left run
            } else {
                hi = mid;     // mid is in the smaller right run, maybe the minimum
            }
        }
        return nums[lo];
    }
};

Complexity Analysis

• Time: O(log n). The search range at least halves every iteration.
• Space: O(1). Only two indices.

Key Insights

1. Two sorted runs: a rotated sorted array is two increasing runs, and every value in the first run is larger than every value in the second.
2. Compare with the right end, not the left: nums[hi] always belongs to the right run (or the array is unrotated), so nums[mid] > nums[hi] cleanly identifies the left run. Comparing with nums[lo] fails on an unrotated array unless you add a special case.
3. hi = mid, not hi = mid - 1: when mid is in the right run it might be the minimum itself, so it must stay in range.
4. Loop until one element remains: with lo < hi as the condition, the answer is nums[lo] when the loop ends, with no extra checks.

Edge Cases

1. Single element: [7] returns 7. The loop never runs.
2. Not rotated (rotated n times): [-4, 0, 5, 8] returns -4. Every comparison moves hi left.
3. Two elements: [2, 1] returns 1 and [1, 2] returns 1.
4. Minimum at the last index: [3, 4, 5, 6, 1] returns 1. Every comparison moves lo right.
5. Negative and extreme values: [5000, -5000] returns -5000. The values never take part in arithmetic, so there is no overflow risk.

Common Mistakes

1. Using hi = mid - 1: this can skip over the minimum when mid is the minimum.
2. Comparing nums[mid] with nums[lo]: nums[mid] >= nums[lo] does not tell you which side holds the minimum when the array is not rotated.
3. Using lo <= hi with hi = mid: the loop never ends once lo == hi.
4. Ignoring the distinctness assumption: with duplicates (LC 154), nums[mid] == nums[hi] is ambiguous and needs hi -= 1, which makes the worst case O(n).
5. Computing mid as (lo + hi) / 2 in fixed-width languages: it is safe here because n <= 5000, but lo + (hi - lo) / 2 is the habit to keep.

Interview Tips

1. Draw the shape: sketch the array as two rising line segments. It makes the nums[mid] versus nums[hi] rule obvious.
2. State the invariant: “the minimum is always within [lo, hi]”. It justifies both update rules and the exit condition.
3. Mention the linear scan first: then explain why the sorted structure allows halving the range.
4. Test on the unrotated case aloud: it is the case most broken solutions get wrong.

Follow-up Questions

1. What if the array can contain duplicates? That is LC 154. When nums[mid] == nums[hi], you cannot tell which side the minimum is on, so shrink with hi -= 1. Worst case becomes O(n), for example [1, 1, 1, 0, 1].
2. How many times was the array rotated? With this page’s definition (k elements moved from the front to the back), the minimum ends up at index (n - k) mod n, so k = (n - index) mod n. Under the other common convention, rotating right by k, the minimum’s index is k itself.
3. Search for a target value? Find the minimum’s index first, then binary search the correct half, or use the one-pass method in Search in Rotated Sorted Array.
4. Find the maximum? It sits just before the minimum: nums[(minIndex - 1 + n) % n].

Related Problems

• Search in Rotated Sorted Array
• Binary Search
• Median of Two Sorted Arrays
• Rotate Array