153. Find Minimum in Rotated Sorted Array LeetCode Solution
In this guide, you will get 153. Find Minimum in Rotated Sorted Array LeetCode Solution with the best time and space complexity. The solution to Find Minimum in Rotated Sorted Array problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Find Minimum in Rotated Sorted Array
Suppose an array of length n sorted in ascending order is rotated between 1 and n times. For example, the array nums = [0,1,2,4,5,6,7] might become:
[4,5,6,7,0,1,2] if it was rotated 4 times.
[0,1,2,4,5,6,7] if it was rotated 7 times.
Notice that rotating an array [a[0], a[1], a[2], …, a[n-1]] 1 time results in the array [a[n-1], a[0], a[1], a[2], …, a[n-2]].
Given the sorted rotated array nums of unique elements, return the minimum element of this array.
You must write an algorithm that runs in O(log n) time.
Example 1:
Input: nums = [3,4,5,1,2]
Output: 1
Explanation: The original array was [1,2,3,4,5] rotated 3 times.
Example 2:
Input: nums = [4,5,6,7,0,1,2]
Output: 0
Explanation: The original array was [0,1,2,4,5,6,7] and it was rotated 4 times.
Example 3:
Input: nums = [11,13,15,17]
Output: 11
Explanation: The original array was [11,13,15,17] and it was rotated 4 times.
n == nums.length
1 <= n <= 5000
-5000 <= nums[i] <= 5000
All the integers of nums are unique.
nums is sorted and rotated between 1 and n times.
Complexity Analysis
Time Complexity: O(\log n)
Space Complexity: O(1)
153. Find Minimum in Rotated Sorted Array LeetCode Solution in C++
class Solution {
public:
int findMin(vector<int>& nums) {
int l = 0;
int r = nums.size() - 1;
while (l < r) {
const int m = (l + r) / 2;
if (nums[m] < nums[r])
r = m;
else
l = m + 1;
}
return nums[l];
}
}; /* code provided by PROGIEZ */
153. Find Minimum in Rotated Sorted Array LeetCode Solution in Java
class Solution {
public int findMin(int[] nums) {
int l = 0;
int r = nums.length - 1;
while (l < r) {
final int m = (l + r) / 2;
if (nums[m] < nums[r])
r = m;
else
l = m + 1;
}
return nums[l];
}
} // code provided by PROGIEZ
153. Find Minimum in Rotated Sorted Array LeetCode Solution in Python
class Solution:
def findMin(self, nums: list[int]) -> int:
l = 0
r = len(nums) - 1
while l < r:
m = (l + r) // 2
if nums[m] < nums[r]:
r = m
else:
l = m + 1
return nums[l] # code by PROGIEZ
