Find Minimum in Rotated Sorted Array
1Try it yourself first
Think for 20-30 minutes before you open any hint. Being stuck is where the learning happens.
Only for you, saved in this browser. After you see the approach you will compare it with your idea.2What is being asked
Find the smallest value in a rotated sorted list (no duplicates) in O(log n).
3Hint ladder
Take one rung at a time. Stop as soon as the idea clicks.
- Hint 1Compare the middle value with the last value. If the middle is bigger, where is the minimum?
- Hint 2If the middle is not bigger than the last value, the minimum is the middle or to its left.
4The approach
Have you tried the hints? The approach is built as a path from the obvious way to the clever one.
The sorted shelf was cut and rotated, so it climbs, then suddenly drops to the smallest book, then climbs again: 4 5 6 7 | 1 2 3. You want the place where it drops (the seam). Look at the middle book and compare it with the LAST book: if the middle is bigger, the drop lies to its right. Otherwise the drop is at the middle or to its left.
- The obvious way
Scan for the smallest value: O(n).
- The key insight
If the middle is bigger than the last value, the list drops somewhere to the right of the middle, so the minimum is on the right. Otherwise the right part is increasing, so the minimum is the middle itself or to the left, and the middle must be kept. Shrink until one value remains.
- The algorithm
- Markers at the two ends.
- Compare the middle with the last value.
- Middle bigger? The minimum is to its right: left marker = middle + 1.
- Otherwise the minimum is at the middle or earlier: right marker = middle. When the markers meet, that value is the minimum.
Watch it run
Examplenumbers = [3, 4, 5, 1, 2]
Middle is 5, last is 2. The middle is bigger, so the drop is to the right. Throw away 3, 4, 5.
range: [1, 2]
Where people slip
- Compare with the LAST value, not the first: comparing with the first gets confused when the list is not rotated at all.
How close was your idea?
You did not write an idea, and that is fine.
Be honest with yourself. This sets your revision list.
5Code
Try writing it yourself from the steps first. Then compare.
def find_min(nums):
low, high = 0, len(nums) - 1
while low < high:
middle = (low + high) // 2
if nums[middle] > nums[high]:
low = middle + 1 # the drop is to the right of the middle
else:
high = middle # the middle could be the minimum
return nums[low]Now close this and write it again from memory, in the language you will use in the interview. Reattempt after 1 day, 7 days and about 30 days.
6Still stuck? Watch a video
Seeing someone explain it out loud can make it click. Try the video after you have read the approach above.