Dare2Solve
Given a sorted array of unique elements that has been rotated at some pivot unknown to you beforehand, find the minimum element in the array. For example, the array [3, 4, 5, 1, 2]
was originally [1, 2, 3, 4, 5]
rotated at the pivot 3
.
The rotated sorted array has a property where the smallest element is the point where the array was rotated. This means that the smallest element is the point where the sequence changes from being larger to smaller.
l
(left) and r
(right), representing the start and end of the array, respectively.m
.l
and r
(i.e., nums[l] < nums[r]
), then the smallest element is nums[l]
.nums[l] <= nums[m]
), move the left pointer to m + 1
to search in the right half.m
.l
will point to the smallest element.(O(\log n)), where (n) is the number of elements in the array. This is because we are using binary search to find the minimum element.
(O(1)), as we are only using a constant amount of extra space for pointers and variables.
class Solution {
public:
int findMin(vector<int>& nums) {
int l = 0;
int r = nums.size() - 1;
while (l < r) {
int m = l + (r - l) / 2;
if (nums[l] < nums[r]) return nums[l];
if (nums[l] <= nums[m]) {
l = m + 1;
} else {
r = m;
}
}
return nums[l];
}
};
class Solution:
def findMin(self, nums: List[int]) -> int:
l, r = 0, len(nums) - 1
while l < r:
m = l + (r - l) // 2
if nums[l] < nums[r]:
return nums[l]
if nums[l] <= nums[m]:
l = m + 1
else:
r = m
return nums[l]
class Solution {
public int findMin(int[] nums) {
int l = 0;
int r = nums.length - 1;
while (l < r) {
int m = l + (r - l) / 2;
if (nums[l] < nums[r]) return nums[l];
if (nums[l] <= nums[m]) {
l = m + 1;
} else {
r = m;
}
}
return nums[l];
}
}
/**
* @param {number[]} nums
* @return {number}
*/
const findMin = function (nums) {
let [l, r] = [0, nums.length - 1];
while (l < r) {
const m = Math.floor((l + r) / 2);
if (nums[l] < nums[r]) return nums[l];
if (nums[l] <= nums[m]) {
l = m + 1;
} else {
r = m;
}
}
return nums[l];
};
console.log(findMin([2, 3, 4, 5, 1]));