Example 1
ready- Input
nums = [ 4, 5, 6, 7, 0, 1, 2 ]- Expected
0- Why
- 0 begins the low-value piece
Find Minimum in Rotated Sorted Array
35 min · findMin()mediumOpen in LeetCode #153 ↗
A sorted shelf has been spun around, but its smallest book still marks the seam.
You're given a non-empty array nums that began in strictly increasing order. It was
then rotated, meaning a prefix — a block from the front — may have been moved to
the end without changing the order inside either piece. Return the smallest value.
The rotation amount is unknown. It may also be zero, leaving the original sorted order untouched.
A few ground rules:
- Every value is distinct.
- The answer is a value, not an index.
- Use the two sorted pieces to avoid scanning the whole array.
Constraints
1 <= nums.length <= 100_000-1_000_000_000 <= nums[i] <= 1_000_000_000- All values are distinct.
numsis a rotation of a strictly increasing array.
Hints
Use the right edge as a compass
Compare the middle value with nums[right]. That rightmost value tells you which
sorted piece contains the middle.
Middle is on the high piece
If nums[middle] > nums[right], the minimum must be strictly to the right of
middle.
Don't throw middle away too soon
Otherwise, middle may itself be the minimum, so keep it with right = middle.
Stop when left == right.
Follow-up
If duplicate values were allowed, which comparison would become ambiguous, and how would that change the worst-case running time?
Visible cases
Examples
Example 2
ready- Input
nums = [ 11, 13, 15, 17 ]- Expected
11- Why
- zero rotation leaves the minimum first
Example 3
ready- Input
nums = [ 2, 1 ]- Expected
1- Why
- with two values, the seam can sit between them
Interview signal
Asked at
AmazonMicrosoftBloomberg
Linear minimum
Keep the smallest value seen while walking through the array.
def find_min(nums: list[int]) -> int:
smallest = nums[0]
for value in nums[1:]:
smallest = min(smallest, value)
return smallestTime O(n). Space O(1). Correct, but it ignores the two sorted runs created by the rotation.
Search the rotation
Keep an interval that contains the minimum and compare its middle value with its right edge.
- If
nums[middle] > nums[right],middlesits on the high-value piece. The seam and minimum are strictly to its right, so setleft = middle + 1. - Otherwise,
middlesits on the low-value piece. It may be the minimum, so preserve it withright = middle.
def find_min(nums: list[int]) -> int:
left, right = 0, len(nums) - 1
while left < right:
middle = left + (right - left) // 2
if nums[middle] > nums[right]:
left = middle + 1
else:
right = middle
return nums[left]When the pointers meet, every discarded position has been proved too high, and the one
remaining index is the rotation seam. The unrotated case works too: every middle value
is below the right edge, so right keeps moving toward index 0.
Time O(log n). Space O(1). Each comparison removes at least half of the remaining interval.
Loading editor
Console
ready to runReady to run.
3 cases are queued.
Visible testcase
Case 1
Expected
0
Run: visible + custom · Submit: full suite