Find Minimum in Rotated Sorted Array
An increasing array of distinct values was rotated zero or more positions. Find its minimum in logarithmic time.
Work through the cases
3 examplesInput notation
Space-separated integers on line 1.Expected result
The minimum value.Case 1
Input
6 8 1 3 4
Expected output
1
Case 2
Input
2 5 9
Expected output
2
Case 3
Input
-1
Expected output
-1
These notes use simplified input/output notation. The linked platform defines the method signature and judge format.
FROM IDEA TO IMPLEMENTATION
Understand the approach.
Compare the documented approaches below. Brute force, better, and optimal versions appear where available; a direct exercise may need only one approach.
A rotated sorted array with distinct values; a linear scan is O(n) and n ≤ 5000 is fine, but order allows log n. The minimum splits the array into two increasing runs. Compare the mid to the last value: larger means the min is on the right, otherwise on the left (including mid). Shrink to one index.
We can use binary search to solve this problem.
First, we define two pointers l and r pointing to the start and end of the array respectively. Then we enter a loop until l is no longer less than r.
In each iteration, we calculate the middle position mid and compare nums[mid] with nums[n-1]. If nums[mid] is greater than nums[n-1], the minimum value is to the right of mid, so we update l to mid + 1. Otherwise, the minimum value is at mid or to its left, so we update r to mid. When the loop ends, pointer l will point to the minimum value, and we return nums[l].
The time complexity is O(log n), where n is the length of array nums. The space complexity is O(1).
class Solution {
public int findMin(int[] nums) {
int l = 0, r = nums.length - 1;
while (l < r) {
int mid = (l + r) >> 1;
if (nums[mid] > nums[nums.length - 1]) {
l = mid + 1;
} else {
r = mid;
}
}
return nums[l];
}
}Reference code. Platform solutions may use supplied node types, imports, or collection libraries; foundational examples are complete programs.
Solutions adapted from Doocs / LeetCode contributors, licensed under CC BY-SA 4.0. Formatting changed; TypeScript versions converted to JavaScript. Supplemental implementations and approach notes added. Adapted solution material is available under the same license.