153. Find Minimum in Rotated Sorted Array
mediumFind the smallest element in a rotated sorted array of distinct integers. Tests whether you can write binary search when there's no explicit 'target' to compare against.
By Sam K., Founder, InterviewChamp.AI · Last verified
Problem
Suppose an array of length n sorted in ascending order is rotated between 1 and n times. For example, the array nums = [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2] if it was rotated 4 times or [0,1,2,4,5,6,7] if it was rotated 7 times. Notice that rotating an array [a[0], a[1], a[2], ..., a[n-1]] 1 time results in the array [a[n-1], a[0], a[1], a[2], ..., a[n-2]]. Given the sorted rotated array nums of unique elements, return the minimum element of this array. You must write an algorithm that runs in O(log n) time.
Constraints
n == nums.length1 <= n <= 5000-5000 <= nums[i] <= 5000All the integers of nums are unique.nums is sorted and rotated between 1 and n times.
Examples
Example 1
nums = [3,4,5,1,2]1Explanation: The original array was [1,2,3,4,5] rotated 3 times.
Example 2
nums = [4,5,6,7,0,1,2]0Explanation: The original array was [0,1,2,4,5,6,7] and it was rotated 4 times.
Example 3
nums = [11,13,15,17]11Explanation: The original array was [11,13,15,17] and it was rotated 4 times.
Solve it now
Free. No sign-up. Python and JavaScript run instantly in your browser.
Hints
Progressive — try the first before opening the next.
Hint 1
There's no explicit target — compare nums[mid] to nums[hi] to decide which side holds the minimum.
Hint 2
If nums[mid] > nums[hi], the minimum is in the right half (mid is in the larger, pre-rotation half).
Hint 3
Otherwise the minimum is in the left half including mid.
Hint 4
Use a half-open window (lo < hi) — when they converge, lo points at the minimum.
Solution approach
Reveal approach
Binary search where the 'target' is the rotation pivot. Use lo = 0, hi = n - 1 with a strict < loop condition. While lo < hi: mid = lo + (hi - lo) / 2. If nums[mid] > nums[hi], the minimum must be strictly right of mid (the pivot lies in (mid, hi]) — set lo = mid + 1. Otherwise nums[mid] <= nums[hi], so the minimum is at mid or to its left — set hi = mid. When lo == hi, return nums[lo]. O(log n) time, O(1) space. Comparing to nums[hi] rather than nums[lo] is the trick — it disambiguates correctly even when the array isn't rotated at all (everything <= nums[hi] sends you left, and lo lands at index 0).
Complexity
- Time
- O(log n)
- Space
- O(1)
Related patterns
- binary-search
Related problems
Asked at
Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).
- Amazon
- Meta
- Microsoft
- Goldman Sachs
More Binary Search practice problems
- 4. Median of Two Sorted Arrays
- 33. Search in Rotated Sorted Array
- 34. Find First and Last Position of Element in Sorted Array
- 35. Search Insert Position
- 69. Sqrt(x)
- 74. Search a 2D Matrix
- 154. Find Minimum in Rotated Sorted Array II
- 162. Find Peak Element