Minimum of a rotated sorted array
Medium · Target 15 minutes · Binary search· Type asked at
Jane Street
Goldman Sachs
Apple
An array of distinct integers was sorted in increasing order, then rotated left
some unknown number of times, so that [0, 1, 4, 5, 6] might arrive as
[4, 5, 6, 0, 1]. Given the rotated array, return its smallest value in
O(log n) time.
Examples
| Input | Output | Why |
|---|---|---|
nums = [3, 4, 5, 1, 2] | 1 | Rotated three positions. |
nums = [11, 13, 15, 17] | 11 | Not rotated at all, which is a rotation of zero. |
nums = [2, 1] | 1 | The smallest input where the rotation matters. |
Constraints
- 1 ≤ n ≤ 5000
- −5000 ≤ nums[i] ≤ 5000
- All values are distinct
- The array is a rotation of a sorted array
Hints
Hint 1
You cannot compare the middle element against a target, because there is no target. What can you compare it against?
Hint 2
Compare nums[mid] against nums[hi]. One of those two comparisons tells you which half the rotation point is in.
Hint 3
If nums[mid] > nums[hi], everything from lo to mid is above the minimum, so the answer is strictly to the right of mid. Otherwise mid could itself be the answer, so keep it.
Where people lose marks
- Writing
hi = mid - 1in the second branch. The minimum can be at mid, and you have just discarded it. - Writing
lo = midin the first branch. With two elements left, mid equals lo and the loop never terminates. - Looping on
lo <= hi. The invariant here is that the answer is always inside [lo, hi], so the loop ends when the range is one element: the condition islo < hi. - Assuming an unrotated array is a special case that needs its own branch. It does not; nums[mid] < nums[hi] handles it.
- This breaks with duplicates. [2, 2, 2, 0, 2] cannot be resolved in O(log n), and the honest answer in an interview is to say so.
Dry run on [5,6,7,8,9,10,1,2,3,4]
Read it one frame at a time, the way you would trace the code on paper in an interview. Each frame shows the state after the step it describes.
-
Step 1 / 6nums50lo6172839410516273849hilo0hi9
The whole array is in range. The answer is somewhere in [0, 9].
-
Step 2 / 6nums50lo61728394mid10516273849himid4nums[mid]9nums[hi]4
nums[4] = 9 > nums[9] = 4. The sequence falls after mid, so the minimum is strictly to the right. Discard [0, 4].
-
Step 3 / 6nums5061728394105lo1627mid3849himid7nums[mid]2nums[hi]4
nums[7] = 2 < nums[9] = 4. From mid to hi is in order, so the minimum is at mid or left of it. Keep mid.
-
Step 4 / 6nums5061728394105lo16mid27hi3849mid6nums[mid]1nums[hi]2
nums[6] = 1 < nums[7] = 2. From mid to hi is in order, so the minimum is at mid or left of it. Keep mid.
-
Step 5 / 6nums5061728394105lo/mid16hi273849mid5nums[mid]10nums[hi]1
nums[5] = 10 > nums[6] = 1. The sequence falls after mid, so the minimum is strictly to the right. Discard [5, 5].
-
Step 6 / 6nums506172839410516lo273849answer1
lo and hi have met at index 6. The minimum is 1.
How to think about it
Binary search does not need sorted input. It needs a question you can ask at the midpoint whose answer eliminates half the array. Here the question is: is the rotation point to my left or to my right?
Compare nums[mid] with nums[hi], the value at the right end of the
current range:
nums[mid] > nums[hi]— the sequence falls somewhere between mid and hi, so the rotation point is in(mid, hi]. Everything up to and including mid is above the minimum. Setlo = mid + 1.nums[mid] < nums[hi]— the stretch from mid to hi is in order, so the minimum is at mid or to its left. Sethi = mid, keeping mid as a candidate.
The range shrinks every step and lo == hi when it stops, which is the answer.
Note the asymmetry: one branch is mid + 1 and the other is plain mid.
That is not a stylistic choice — writing hi = mid - 1 throws away the answer, and
writing lo = mid loops for ever.
Why compare against hi and not lo? Because the
comparison against lo is ambiguous when the array is not rotated at all. Against
hi there is no such case.
Complexity. Time O(log n) · Space O(1)
The solution, in six languages
Each one is compiled and run against the test table before it is published. Java is reviewed by hand.
def rotated_minimum(nums):
lo, hi = 0, len(nums) - 1
while lo < hi:
mid = (lo + hi) // 2
if nums[mid] > nums[hi]:
lo = mid + 1 # the fall is to the right of mid
else:
hi = mid # mid may itself be the minimum, so keep it
return nums[lo]#include <vector>
int solve(const std::vector<int>& nums) {
int lo = 0, hi = static_cast<int>(nums.size()) - 1;
while (lo < hi) {
const int mid = lo + (hi - lo) / 2; // no overflow on large indices
if (nums[mid] > nums[hi]) lo = mid + 1; // the fall is right of mid
else hi = mid; // mid may be the minimum
}
return nums[lo];
}class Solution {
public int rotatedMinimum(int[] nums) {
int lo = 0, hi = nums.length - 1;
while (lo < hi) {
int mid = lo + (hi - lo) / 2; // no overflow on large indices
if (nums[mid] > nums[hi]) lo = mid + 1; // the fall is right of mid
else hi = mid; // mid may be the minimum
}
return nums[lo];
}
}function rotatedMinimum(nums) {
let lo = 0, hi = nums.length - 1;
while (lo < hi) {
const mid = (lo + hi) >> 1;
if (nums[mid] > nums[hi]) lo = mid + 1; // the fall is to the right of mid
else hi = mid; // mid may be the minimum, keep it
}
return nums[lo];
}fn solve(nums: &[i64]) -> i64 {
let (mut lo, mut hi) = (0usize, nums.len() - 1);
while lo < hi {
let mid = lo + (hi - lo) / 2;
if nums[mid] > nums[hi] {
lo = mid + 1; // the fall is right of mid
} else {
hi = mid; // mid may itself be the minimum
}
}
nums[lo]
}import Data.Array
solve :: [Int] -> Int
solve nums = arr ! go 0 (n - 1)
where
n = length nums
arr = listArray (0, n - 1) nums
go lo hi
| lo >= hi = lo
| arr ! mid > arr ! hi = go (mid + 1) hi -- the fall is right of mid
| otherwise = go lo mid -- mid may be the minimum
where mid = lo + (hi - lo) `div` 2Variants to try
- Allow duplicates: the comparison can be a tie, and the only safe move is hi -= 1, which is O(n) in the worst case.
- Search for a given value in the rotated array rather than the minimum: find the rotation point, then binary search the correct half.
- Return the number of rotations rather than the value: it is the index of the minimum.
- A rotated array that was sorted in decreasing order: the same argument with the inequalities flipped.
Next problems
Find a value in a rotated sorted array
Split any range at its middle and one side is in order. Test whether the target lies in that side; if not, it lies in the other.
Open the problem → Medium20 minSearch a rotated array with repeated values
When the two ends and the middle are equal, no comparison can say which half is sorted. Shrink both ends by one and carry on.
Open the problem → Easy10 minFind a value in a sorted array
The search every other binary search is built on: halve a closed range until the value is found or the range is empty.
Open the problem →Write a solution and run it against the real test table.
Keep going
Find a value in a rotated sorted array
Split any range at its middle and one side is in order. Test whether the target lies in that side; if not, it lies in the other.
Open the problem → Medium20 minSearch a rotated array with repeated values
When the two ends and the middle are equal, no comparison can say which half is sorted. Shrink both ends by one and carry on.
Open the problem → Easy10 minFind a value in a sorted array
The search every other binary search is built on: halve a closed range until the value is found or the range is empty.
Open the problem → Binary searchThe pattern behind it
Search the answer, not the array: halve a monotone predicate until one candidate is left.
Read the pattern →Preparing for a real process? Quant interview preparation, or book a free 20-minute call.