153. Find Minimum in Rotated Sorted Array
Asked at Amazon
Difficulty
Medium
Time
O(log n)
Space
O(1)
Pattern
Array
Companies
1
Problem
You are given an array of unique numbers. The array was originally sorted in increasing order, then it was rotated some number of times. A rotation moves the last element to the front, and this can happen anywhere from 1 to n times.
Because of the rotation, the array looks like two increasing runs joined together. For example, [0,1,2,4,5,6,7] rotated 4 times becomes [4,5,6,7,0,1,2]. The smallest value sits at the point where the array drops.
Return the minimum element in the array. Your algorithm must run in O(log n) time, so a plain scan over all elements is not good enough.
A sorted array with one drop
Constraints
- ●
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.
Examples
nums = [3,4,5,1,2]1nums = [4,5,6,7,0,1,2]0nums = [11,13,15,17]11Asked At
1 companies| Company | Difficulty | |
|---|---|---|
| Amazon | Medium | View all Amazon questions → |
How to Think About It
A linear scan finds the minimum in O(n), but binary search can do it in O(log n).
Think about what distinguishes the minimum element from the rest — it is the only element smaller than its predecessor.
Compare nums[mid] with nums[right] to decide which half contains the minimum.
If nums[mid] > nums[right], the minimum is in the right half. Otherwise, it is in the left half including mid.
The search converges when left meets right, and that position holds the minimum.
Optimal Approach
Use binary search with two pointers at the start and end. Compare nums[mid] with nums[right]. If nums[mid] is greater, the minimum must be to the right (mid + 1 to right). If nums[mid] is less than or equal, the minimum is at mid or to the left (left to mid). When left meets right, that index holds the minimum. This runs in O(log n) time and O(1) space.
Binary search toward the drop
What Trips People Up in Real Interviews
Ask whether the array is guaranteed to be rotated (not just sorted) — if not rotated, the first element is the answer.
Explain the binary search logic clearly using the comparison of mid and right pointers.
Mention that comparing with the left pointer instead also works but comparing with right is cleaner.
Discuss why there are no duplicates — duplicates would require a modified approach with O(n) worst case.
Edge cases: array not rotated at all, rotated by one position, only two elements.
Solution Code
O(log n) timedef findMin(nums):
left, right = 0, len(nums) - 1
while left < right:
mid = (left + right) // 2
if nums[mid] > nums[right]:
left = mid + 1
else:
right = mid
return nums[left]Frequently Asked Questions
What is the Find Minimum in Rotated Sorted Array problem?
Given a sorted array that has been rotated at some pivot unknown to you beforehand, find the minimum element. The array contains no duplicate elements.
How do you solve Find Minimum in Rotated Sorted Array?
The optimal approach runs in O(log n) time and O(1) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.
What companies ask Find Minimum in Rotated Sorted Array?
Find Minimum in Rotated Sorted Array is asked at Amazon. It is a medium difficulty problem.
What are common mistakes on Find Minimum in Rotated Sorted Array?
- Ask whether the array is guaranteed to be rotated (not just sorted) — if not rotated, the first element is the answer.
- Explain the binary search logic clearly using the comparison of mid and right pointers.
- Mention that comparing with the left pointer instead also works but comparing with right is cleaner.
- Discuss why there are no duplicates — duplicates would require a modified approach with O(n) worst case.
- Edge cases: array not rotated at all, rotated by one position, only two elements.