Find Minimum in Rotated Sorted Array

Problem in Plain English

Given a rotated sorted array of unique integers, return its smallest element. Comparing the middle against the right end reveals which half holds the rotation point, giving a logarithmic search.

Problem Statement

Suppose an array of length n sorted in ascending order is rotated between 1 and n times. For example, the array nums = [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2] if it was rotated 4 times.

Given the sorted rotated array nums of unique elements, return the minimum element of this array. You must write an algorithm that runs in $O(\log n)$ time.

Constraints

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

Examples

Example 1

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

The values rise from 3 through 5, then drop to 1 at index 3. Every other value is larger, so return the value 1, not its index 3.

Example 2

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

The minimum 0 is inside the array at index 4, after the drop from 7. It remains the answer even though both endpoints are larger.

Example 3

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

A full-length rotation preserves increasing order. There is no internal drop, so the first value 11 is the minimum.

Example 4

Input: nums = [-5]
Output: -5

With one element, that value is necessarily the minimum. The binary-search loop runs zero times.

Intuition

Rotation cuts a strictly increasing array into two increasing pieces; when a drop exists, the first value after it is the minimum. In [3, 4, 5, 1, 2], that value is 1. Scanning finds it by checking every value. Binary search instead keeps an interval containing the minimum and compares its middle with its right endpoint to remove half the candidates.

Approaches

Scan For Minimum

Solution Details

Reveal Scan For Minimum: intuition, complexity, and code

Intuition

Keep the smallest value seen while visiting every entry. This works even without sortedness, but examining the entire input takes linear time and misses the required logarithmic bound.

Step-by-Step Logic

Initialize min from nums[0]; on Example 1, [3, 4, 5, 1, 2], it starts at 3.
Visit every value in order and replace min only if the value is smaller. Reading 3, 4, and 5 leaves min = 3.
Continue through the remaining values: reading 1 changes min from 3 to 1; reading 2 leaves it at 1.
After all entries have been visited, return the running minimum. Example 1 returns 1.

Why It Works

After each visit, min is the smallest of all values visited so far. It is initialized to a real input value; comparing the next value preserves this rule by retaining the smaller of it and the previous minimum. Every entry is eventually visited, so the final minimum is the smallest value in the entire array.

Dry Run

Scan For Minimum: variable states at each step
Phase	Current value	min before	min after / return
Initialize	nums[0] = 3	unset	3
Visit index 0	3	3	3
Visit index 1	4	3	3
Visit index 2	5	3	3
Visit index 3	1	3	1
Visit index 4	2	1	1
End of scan	none	1	return 1

Complexity Analysis

Time Complexity

O(n)

Space Complexity

O(1)

Let n be nums.length. The loop visits all n entries and performs constant work on each, giving O(n) time. The running minimum, current value, and iterator use O(1) extra space; no copy, slice, collection, or recursion is allocated. The returned value is a scalar. This baseline does not meet the required O(log n) time.

Code

Solution.java

1class Solution {2    public int findMin(int[] nums) {3        int min = nums[0];4        for (int num : nums) {5            min = Math.min(min, num);6        }7        return min;8    }9}

Hints

Hint 1

Where does a rotated increasing array stop rising? A full rotation may leave no internal drop.

Hint 2

Keep an inclusive interval containing the minimum. Compare its middle with its current right endpoint.

Hint 3

If nums[mid] > nums[right], move left to mid + 1; otherwise retain mid by moving right to mid.

Edge Cases

An unrotated array such as [11, 13, 15, 17] keeps moving the right boundary left until index 0.
A two-element rotation like [2, 1] resolves in a single middle-against-right comparison.
A single element skips the loop entirely and returns that entry.

Common Mistakes and Interview Tips

Using right = mid - 1 can discard the minimum itself: in [3, 1, 2], mid already holds 1.
Using left = mid can stall on two candidates such as [2, 1]; the larger middle is safely excluded with mid + 1.
Looping with left <= right and right = mid never shrinks a singleton. Stop when the boundaries meet.
Returning left gives an index, but this problem asks for nums[left], the value.
Applying this discard rule to duplicate values is unsafe: equal middle and right values do not reveal which side contains the minimum. Uniqueness is essential.
Interview tip: explain which candidate is excluded in each branch and why mid must stay in the smaller-middle branch. Comparing with the left endpoint can support other algorithms, but needs a different invariant.

Key Takeaway

In rotated sorted arrays the right end anchors the search: the middle against the right end tells you which half holds the rotation point.