Find Minimum in Rotated Sorted Array
Trays on a circular conveyor belt carry distinct labels that increase all the way around the loop, except at one spot where the largest label is followed by the smallest. A camera reads every label once, starting from whichever tray happens to be in front of it, and produces the array nums. If the camera starts at the smallest label, nums is fully sorted; otherwise it looks like [40,55,7,18,26].
Return the smallest label in nums. Your solution must run in O(log n) time.
Input: nums = [18,26,33,4,11] Output: 4
Explanation: The labels drop from 33 to 4, so 4 is where the loop starts again.
Input: nums = [9,1,3,5,7] Output: 1
Explanation: The drop comes right after the first tray.
Input: nums = [-6,-2,0,8] Output: -6
Explanation: The camera started at the smallest label, so the array is already sorted.
Constraints
numsholds between 1 and 5000 labels.- Labels are distinct integers from -5000 to 5000.
numsis an ascending list read from some starting point on the loop, possibly the smallest label.
💡 Hint 1
The minimum is the only element smaller than the one before it, the point where the array "drops". A linear scan finds it, but you can do better.
💡 Hint 2
Compare nums[mid] with nums[hi]. If nums[mid] is larger, the drop must be somewhere to the right of mid.
💡 Hint 3
Otherwise mid itself might be the minimum, so keep it in the window: hi = mid rather than mid - 1.
Try it yourself first ✎
Solutions stick better after a real attempt. Peek when you're ready.
Approach
Binary search for the rotation point by comparing the middle element with the last element of the window. If nums[mid] > nums[hi], the values wrap around somewhere after mid, so the minimum lies in (mid, hi] and lo = mid + 1. Otherwise [mid, hi] is ascending, so nothing right of mid can beat nums[mid], and hi = mid keeps mid as a candidate. The loop runs while lo < hi; when the window shrinks to one index, that index holds the minimum.
function findMin(nums) {
let lo = 0;
let hi = nums.length - 1;
while (lo < hi) {
const mid = (lo + hi) >> 1;
if (nums[mid] > nums[hi]) lo = mid + 1;
else hi = mid;
}
return nums[lo];
}class Solution {
public int findMin(int[] nums) {
int lo = 0, hi = nums.length - 1;
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (nums[mid] > nums[hi]) lo = mid + 1;
else hi = mid;
}
return nums[lo];
}
}No submissions yet. Press Submit to run your code against every test.
/**
* @param {number[]} nums
* @return {number}
*/
function findMin(nums) {
}Run your code to see results here.