🎨Now live: Try our Free AI Image Generation Feature

Description
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
.
Intuition
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.
Approach
- Initialize Pointers: Start with two pointers,
l
(left) andr
(right), representing the start and end of the array, respectively. - Binary Search:
- Calculate the middle index
m
. - If the array is already sorted betweenl
andr
(i.e.,nums[l] < nums[r]
), then the smallest element isnums[l]
. - If the left half is sorted (nums[l] <= nums[m]
), move the left pointer tom + 1
to search in the right half. - Otherwise, the minimum element must be in the left half, so move the right pointer tom
. - Return Result: Once the loop exits,
l
will point to the smallest element.
Complexity
Time Complexity:
(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.
Space Complexity:
(O(1)), as we are only using a constant amount of extra space for pointers and variables.
Code
C++
class Solution {
public:
int findMin(vector& 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];
}
};
Python
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]
Java
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];
}
}
JavaScript
/**
* @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]));