Find Minimum in Rotated Sorted Array
A medium Arrays problem included in Love Babbar 450, Striver A2Z. Below: the roles whose interviews prioritise this topic, and how to practise it.
- Topic
- Arrays
- Sheets
- 2
- Core for
- 25 roles
- Platform
- LeetCode
The problem
Given a rotated sorted array that was originally sorted in ascending order, find the minimum element in O(log n) time.
Example 1
- Input
- [3,4,5,1,2]
- Output
- 1
Example 2
- Input
- [4,5,6,7,0,1,2]
- Output
- 0
Example 3
- Input
- [1]
- Output
- 1
Constraints
- 1 <= n <= 5*10^4
- -10^5 <= arr[i] <= 10^5
How to think about it
Updated 2026-09-09The inflection point is the only place in the array where ascending order breaks. Comparing the midpoint against the rightmost element cleanly reveals which half contains that drop: if the middle is greater than the right end, the minimum must lie strictly to the right; otherwise, it lies at or to the left of the middle.
Approaches, worst first
Linear inflection scan
time O(n) · space O(1)
Iterate from index 0 to n - 1 checking for the first element smaller than its predecessor, or track a running minimum. Simple and failsafe, but inspects every element and forfeits the logarithmic speedup made possible by the sorted segments.
Binary search against right boundaryWrite this one
time O(log n) · space O(1)
Set low = 0 and high = n - 1. While low < high, compute mid. If arr[mid] > arr[high], the pivot must be in the right half so low = mid + 1; otherwise, the pivot is at mid or to its left, so high = mid. When low equals high, arr[low] is the minimum.
Where people lose marks · 3
- Comparing arr[mid] against arr[low] instead of arr[high] fails on unrotated or fully rotated arrays where arr[low] < arr[high].
- Setting high = mid - 1 instead of high = mid can discard the minimum when mid itself is the smallest element.
- A single-element array where low equals high on entry must terminate immediately without loop index errors.
Full solution
Binary search against the right boundary: arr[mid] > arr[high] means the drop is to the right, otherwise mid or something left of it is the minimum. Comparing to arr[high] (not arr[low]) is what keeps unrotated input correct, and high = mid (not mid - 1) never discards the answer.
Python
def find_min(arr: list[int]) -> int:
low, high = 0, len(arr) - 1
while low < high:
mid = (low + high) // 2
if arr[mid] > arr[high]:
low = mid + 1 # drop is to the right of mid
else:
high = mid # mid may itself be the minimum, keep it
return arr[low]
JavaScript
function findMin(arr) {
let low = 0;
let high = arr.length - 1;
while (low < high) {
const mid = Math.floor((low + high) / 2);
if (arr[mid] > arr[high]) {
low = mid + 1; // drop is to the right of mid
} else {
high = mid; // mid may itself be the minimum, keep it
}
}
return arr[low];
}
The theory behind it
Arrays — the ground this problem stands on. All Arrays problems
What Arrays is
An array is a row of fixed boxes laid side by side in computer memory, like numbered lockers in a hallway. Because each box occupies identical space and sits directly next to its neighbors, jumping to locker zero or locker ten thousand takes the exact same tiny fraction of time. Every box holds an item of the same type, addressed by an offset number called an index.
When to reach for it
Reach for an array when items arrive in a known sequence and need immediate retrieval by position number. Problems asking for running totals, prefix accumulations, cyclic rotations, or in-place rearrangements signal array mechanics. Whenever constraints require constant-time random lookups or contiguous cache scans across fixed collections, a flat sequence is the default container.
How the pattern works
Visualize a tape with zero-indexed slots stretching from start to end. Keep track of write and read cursors when modifying contents without allocating helper buffers. For running computations, maintain an invariant such as having processed all elements left of the current index while pending elements wait to the right. When modifying entries in place, consider scanning backwards from the end so unread data is not overwritten.
What each operation costs
| Operation | Time |
|---|---|
| look up element by index | O(1) |
| insert or delete at the start | O(n) |
| search an unsorted collection for a value | O(n) |
What usually goes wrong with Arrays
- Reading past the final index by checking index less than or equal to length instead of strictly less than length, triggering index out of bounds exceptions.
- Modifying length or removing elements during a forward iteration loop, which causes remaining items to shift left and skip validation on the next neighbor.
- Assuming dynamic resizing is costless inside nested loops, causing repeated memory reallocation copies when appending unknown quantities of items.
Which roles need this problem
Arrays is a core topic for these 25 roles — if you're targeting one of them, this problem is early in your path, not optional.
Secondary for 3 more roles, including Database Engineer, Bioinformatics Engineer, Networking Engineer.
Track this in your role's order
Pick your target role and all 370 problems — including this one — resequence to what that interview actually asks. Free.
Start freeMore Arrays problems
Problem set and role mapping as of .