153. Find Minimum in Rotated Sorted Array
mediumAsked at CiscoFind Minimum in Rotated Sorted Array at Cisco is a modified-binary-search problem. The interviewer is checking whether you reach for log-n directly rather than scanning, and whether you correctly identify which half of the array contains the rotation pivot.
By Sam K., Founder, InterviewChamp.AI · Last verified
Source citations
Public interview reports confirming this problem appears in Cisco loops.
- Glassdoor (2026-Q1)— Cisco SDE-II onsite reports cite this as a 30-minute binary-search round.
- Blind (2025-10)— Cisco interview thread lists Find Minimum in Rotated Sorted Array as a recurring problem.
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. 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]1Example 2
nums = [4,5,6,7,0,1,2]0Example 3
nums = [11,13,15,17]11Explanation: Rotated n times = identity; minimum is the first element.
Approaches
1. Brute-force linear scan
Walk the array once, track the min.
- Time
- O(n)
- Space
- O(1)
function findMinBrute(nums) {
let best = nums[0];
for (let i = 1; i < nums.length; i++) {
if (nums[i] < best) best = nums[i];
}
return best;
}Tradeoff: Correct but violates the rubric — Cisco requires O(log n). Use only to anchor the problem before optimizing.
2. Modified binary search (optimal)
Compare nums[mid] to nums[right]. If nums[mid] > nums[right], the rotation point (and the minimum) is in the right half. Otherwise it's in the left half (including mid).
- Time
- O(log n)
- Space
- O(1)
function findMin(nums) {
let left = 0, right = nums.length - 1;
while (left < right) {
const mid = (left + right) >> 1;
if (nums[mid] > nums[right]) {
left = mid + 1;
} else {
right = mid;
}
}
return nums[left];
}Tradeoff: Pure log(n) binary search. The trick: compare to nums[right], NOT nums[left] — nums[left] vs nums[mid] is ambiguous on a non-rotated array. The 'while (left < right)' (strict less-than) and `right = mid` (not mid - 1) are the gotchas — together they converge to the minimum without overshooting.
Cisco-specific tips
Cisco interviewers grade this on whether you compare to nums[right] specifically. State the invariant out loud: 'I compare nums[mid] to nums[right]. If mid > right, the minimum must be to the right of mid — so left = mid + 1. Otherwise the minimum is mid or to its left — so right = mid (NOT mid - 1, because mid itself could BE the minimum).' That sentence is the entire interview signal.
Common mistakes
- Comparing nums[mid] to nums[left] — fails on the non-rotated case [1,2,3,4,5] because nums[mid] > nums[left] is always true.
- Writing `right = mid - 1` instead of `right = mid` — overshoots the minimum.
- Using `<=` in the while loop — converges to a single element but you never exit; you exit because `left === right` and that's the answer.
Follow-up questions
An interviewer at Cisco may pivot to one of these next:
- Find Minimum in Rotated Sorted Array II (LC 154) — array has duplicates; can't binary-search cleanly when nums[mid] == nums[right], must linearly skip.
- Search in Rotated Sorted Array (LC 33) — find a target value, not the min.
- Search in Rotated Sorted Array II (LC 81) — search with duplicates.
- Peak Element (LC 162) — different binary-search variant; comparison neighbor-to-neighbor.
Solve it now
Free. No sign-up. Python and JavaScript run instantly in your browser.
FAQ
Why compare to nums[right] specifically?
Because the answer (the rotation pivot, which is also the minimum) is always less than or equal to nums[right]. If nums[mid] > nums[right], the pivot is in (mid, right] — strictly right of mid. If nums[mid] <= nums[right], the pivot is in [left, mid] — at or left of mid. nums[left] doesn't give you that clean cut on the non-rotated case.
What if there are duplicates?
Different problem (LC 154). When nums[mid] == nums[right], you can't tell which half holds the pivot, so you fall back to `right--` and accept O(n) worst case. Cisco interviewers may ask 'what if duplicates?' as a follow-up — be ready to acknowledge the algorithm degrades to linear.
Free learning resources
Curated free links for this problem.