#153 Find Minimum in Rotated Sorted Array
the problem
In plain words
A sorted array of unique values was rotated 1 to n times. Return its minimum element in O(log n).
in nums = [3,4,5,1,2]
out 1
in nums = [4,5,6,7,0,1,2]
out 0
in nums = [11,13,15,17]
out 11
Rotated n times — back to sorted.
- 1 ≤ n ≤ 5000
- -5000 ≤ nums[i] ≤ 5000
- All unique
your turn
Try it before you peek
Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.
Solve it in the browser
LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.
Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.
Marking the problem solved, or opening every hint, also shows it.
the aha
Key insight
patternModified binary search
Compare nums[mid] with nums[hi]. If mid is bigger, the drop (and the minimum) is to the right. Otherwise mid..hi is sorted and the minimum is mid or to its left.
solutions
From brute force to optimal
Track the smallest value seen.
- min = nums[0]; for each x, min = Math.min(min, x).
Every element once.
One variable.
class Solution { public int findMin(int[] nums) { int min = nums[0]; for (int x : nums) min = Math.min(min, x); return min; }}Boundary template: shrink [lo, hi] until it holds only the minimum.
- lo = 0, hi = n−1; while lo < hi.
- nums[mid] > nums[hi] → lo = mid + 1.
- Else → hi = mid.
- Return nums[lo].
Halves each step.
Three indices.
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; // a drop lies right of mid: min is there else hi = mid; // mid..hi is sorted: min is mid or left } return nums[lo]; // lo == hi: the minimum }}Dry run
in the room
How to say it in the interview
talk track
- Explain why we compare with
hi, notlo: an unrotated array has nums[mid] > nums[lo] too, which would wrongly send us right.
traps
- Comparing with nums[lo] — breaks on arrays that aren't rotated.
hi = mid − 1— could skip the minimum when it is mid.
what they ask next
Follow-ups
With duplicates (LC 154)?
If nums[mid] == nums[hi], you can't decide — do hi-- (safe because nums[mid] is an equal copy). Worst case O(n).
before you submit
Edge cases to test
- Not rotated (or rotated n times): the minimum is nums[0].
- Two elements: [2, 1] → 1.
- One element.
practise next
Similar problems
- #33Search in Rotated Sorted ArrayMediumin Binary Search
- #162Find Peak ElementMediumin Binary Search