A sorted array of unique integers has been rotated somewhere between 1 and n times. Rotating once moves the last element to the front: [a[0], a[1], ..., a[n-1]] becomes [a[n-1], a[0], a[1], ..., a[n-2]].
For example, [0,1,2,4,5,6,7] might appear as:
[4,5,6,7,0,1,2] after 4 rotations.[0,1,2,4,5,6,7] after 7 rotations (a full cycle lands it back where it started).Given the rotated array nums, return the minimum element.
A linear scan is easy — your algorithm must run in O(log n) time.
[1,2,3,4,5] (fully rotated, so sorted) and in [3,4,5,1,2], nums[mid] > nums[lo] holds in both — yet the minimum is on opposite sides. nums[hi] gives an unambiguous signal: nums[mid] > nums[hi] means the drop is right of mid, otherwise it is at mid or left.nums[mid] < nums[hi], index mid might itself hold the minimum — you have not ruled it out. hi = mid - 1 could step past the answer. The asymmetry is safe: in the other branch nums[mid] > nums[hi] proves mid is not the minimum, so lo = mid + 1 is fine.[11,13,15,17]. Then nums[mid] < nums[hi] on every step, hi walks down to 0, and the algorithm correctly returns nums[0] — no special case needed.lo == hi == 0 the loop never runs and nums[0] is returned immediately.nums[mid] == nums[hi] becomes ambiguous — you cannot tell which side the drop is on. The fix is to shrink conservatively: hi -= 1 on ties. Worst case (all equal values) degrades to O(n), which is provably unavoidable.lo instead of nums[lo].[lo, hi] is fully sorted — check whether the target lies inside that sorted half, and recurse into the correct side. That is exactly Search in Rotated Sorted Array.Input: nums = [3,4,5,1,2] Output: 1 The original array was [1,2,3,4,5], rotated 3 times. The minimum is 1.
Input: nums = [4,5,6,7,0,1,2] Output: 0 The original array was [0,1,2,4,5,6,7], rotated 4 times. The minimum is 0.
Input: nums = [11,13,15,17] Output: 11 Rotated 4 times — a full cycle — so the array is still fully sorted and the minimum is the first element.
- 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.
This problem is the purest form of a big idea: binary search doesn't need a target — it only needs a question whose answer tells you which half to throw away. Master the compare-with-the-right-end trick here and two harder rotated-array problems fall like dominoes.
lo < hi / hi = mid template that shrinks a range to a single index instead of hunting a target.[lo, hi].Formally: nums was sorted ascending, then rotated between 1 and n times (rotating n times restores the sorted order). All values are unique. Return the smallest value in O(log n).
Worked example — nums = [4,5,6,7,0,1,2]
index: 0 1 2 3 4 5 6
value: 4 5 6 7 | 0 1 2
└ run 1 ──┘ └ run 2 ┘
drop here ↑
minimum = 0 (start of the second run)
A senior candidate pins down the input's shape before writing a single line — it is exactly those guarantees that make O(log n) possible.
“Are all elements guaranteed to be unique?”
Yes — and it matters. With duplicates, nums[mid] == nums[hi] is ambiguous and the worst case degrades to O(n).
“Is the array guaranteed to be a rotation of a sorted array?”
Yes. On an arbitrary array the halving logic is meaningless — the whole algorithm rests on this promise.
“Can the array have just one element?”
Yes, n >= 1. The loop should simply not run and return that element.
“What if the array was rotated n times and is fully sorted?”
Perfectly valid input — the minimum is nums[0]. This case is exactly why comparing mid against the right end beats comparing against the left.
“How large can n get?”
Up to 5000. A linear scan passes on size alone — but the statement demands O(log n), so binary search is the real deliverable.
Before I code, let me confirm the guarantees.
The array is a rotation of a strictly increasing array, so every element is unique — correct?
A full rotation is allowed, so the array may already be sorted — I will make sure my search handles that case.
Since you want O of log n, I will binary search for the rotation point rather than scan.
A sorted array rotated once or more splits into two sorted runs. Scanning left to right, values increase, fall off a cliff exactly once, then increase again. The element at the bottom of that cliff — the start of the second run — is the global minimum.
4 5 6 7 | 0 1 2
↑ the only place nums[i] > nums[i+1]If the array was rotated a full n times there is no cliff at all — the array is sorted and the minimum is simply the first element.
Stand at any index mid and peek at the last element:
nums[mid] > nums[hi] — you are on the first run (the high plateau). The drop, and therefore the minimum, is strictly to your right: lo = mid + 1.nums[mid] < nums[hi] — you are on the second run (or the array is sorted). The minimum is at mid or to its left: hi = mid.Equal is impossible while lo < hi because all elements are unique. Either way, half the range disappears — that is the entire binary search.
Comparing with nums[lo] is ambiguous: in [1,2,3,4,5] (rotated n times) you get nums[mid] > nums[lo], and in [3,4,5,1,2] you also get nums[mid] > nums[lo] — same signal, minimum on opposite sides. The right end never lies: nums[mid] versus nums[hi] cleanly separates before the drop from at-or-after the drop, and the sorted case falls out for free.
| Brute force | Optimal | |
|---|---|---|
| Idea | Scan every element, track the smallest | Binary search for the drop using nums[mid] vs nums[hi] |
| Time | O(n) | O(log n) |
| Space | O(1) | O(1) |
Full, runnable code for both approaches lives in the Approaches selector below.
Key takeaway
Binary search generalises beyond find a target: any time one comparison can tell you which half cannot contain the answer, you can halve the range. Here that comparison is nums[mid] versus nums[hi] — the compare-with-the-right-end trick that also unlocks searching a target in a rotated array.
lo, hi = 0, n - 1
while lo < hi:
mid = (lo + hi) / 2
if nums[mid] > nums[hi]: lo = mid + 1 # drop is to the right
else: hi = mid # min at mid or left
return nums[lo]