-
Notifications
You must be signed in to change notification settings - Fork 0
062 — Find Minimum in Rotated Sorted Array
LeetCode 153 · Medium. Suppose an array of length n, sorted in ascending order with distinct values, is rotated between 1 and n times. Given the rotated array nums, return the minimum element, in O(log n) time.
The minimum of a rotated sorted array sits at exactly one place: the "seam" where the rotation cut the array — the one spot where a smaller value follows a larger one. Everywhere else, the array is locally increasing. So the question isn't "scan for the smallest value," it's "find the seam." And the seam can be hunted the same way any target is hunted with Binary Search: at each midpoint, a single comparison against the segment's right endpoint tells you whether the seam is to the left of mid or at/to the right of it, letting you throw away the half that's guaranteed not to contain it.
"Rotated sorted array" plus "find the minimum" (rather than "find a target") is a variant of the same rotated-array family as chapter 61, but the monotonic condition being binary searched is different: instead of "is target in this half," it's "does this half still contain the rotation point?" Comparing nums[mid] against nums[hi] is the tell — if nums[mid] > nums[hi], the seam (and the minimum) must be strictly to the right of mid; otherwise the right half from mid onward is already fully sorted and the minimum is mid or further left.
Scan for the smallest value.
func findMinBruteForce(_ nums: [Int]) -> Int {
var minValue = nums[0]
for value in nums {
if value < minValue {
minValue = value
}
}
return minValue
}
// smoke test
print(findMinBruteForce([3, 4, 5, 1, 2])) // 1
print(findMinBruteForce([4, 5, 6, 7, 0, 1, 2])) // 0Big-O: O(n) time, O(1) space.
Binary search for the rotation seam by comparing the midpoint against the segment's right endpoint.
func findMin(_ nums: [Int]) -> Int {
var lo = 0
var hi = nums.count - 1
while lo < hi {
let mid = lo + (hi - lo) / 2
if nums[mid] > nums[hi] {
// the seam (and the minimum) is strictly to the right of mid
lo = mid + 1
} else {
// nums[mid] <= nums[hi]: this half is already sorted — minimum is mid or to its left
hi = mid
}
}
return nums[lo]
}
// smoke test
print(findMin([3, 4, 5, 1, 2])) // 1
print(findMin([4, 5, 6, 7, 0, 1, 2])) // 0
print(findMin([11, 13, 15, 17])) // 11 (no rotation)Big-O: O(log n) time, O(1) space.
Every comparison of nums[mid] to nums[hi] answers exactly one question: "is the segment [mid...hi] already sorted, or does the rotation seam still live inside it?" If nums[mid] > nums[hi], the seam must be somewhere in (mid, hi], because a properly sorted segment could never have its first element bigger than its last — so the minimum is provably not at or before mid, and the left half (including mid) is discarded. If nums[mid] <= nums[hi], the segment [mid...hi] is confirmed sorted, meaning the seam (if there is one at all) is at or before mid — so the right half beyond mid is discarded instead. Either branch eliminates half the array with certainty, which is what keeps this O(log n) instead of the brute force's O(n) full scan.
- Binary Search — same halving template, with "is the rotation seam in this half?" replacing the usual target comparison.
-
Arrays & Strings — the underlying array and its
O(1)indexed access. - Search in Rotated Sorted Array — the sibling problem that searches for an arbitrary target in the same kind of rotated array, using the same "which half is sorted" reasoning.
The minimum of a rotated sorted array lives at the one seam where a big value drops to a small one — binary search for that seam by asking "is the right half of what's left still sorted?"
For nums = [4, 5, 6, 7, 0, 1, 2], trace lo, hi, mid, and the comparison nums[mid] vs. nums[hi] at each step until lo == hi. What happens if the array isn't rotated at all (e.g. [1, 2, 3, 4, 5]) — does the algorithm still terminate at the correct answer, and why?
⬅️ Previous: Search in Rotated Sorted Array · Next: Time Based Key-Value Store ➡️