153. Find Minimum in Rotated Sorted Array Leetcode Solution
Find Minimum in Rotated Sorted Array Leetcode Problem :
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.
Find Minimum in Rotated Sorted Array Leetcode Solution:
Constraints :
- 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.
Example 1:
- Input: nums = [4,5,6,7,0,1,2]
- Output: 0
Example 2:
- Input: nums = [11,13,15,17]
- Output: 11
Approach :
Using binary search, all you need to know is that if nums[r] > nums[l], then you got a sorted array and the minimum value is nums[l], hence the while loop condition is nums[l] > nums[r], which basically means nums[l] is not the smallest value and you have two subarrays of monotonically increasing numbers. The first element of second subarray is the smallest value, so you want to find that.
Now if nums[l] <= nums[m], this means m is in the first subarray, so the second subarray or just the minimum value is in the range [m + 1, r], so set l = m + 1. This also includes the case when l == m, that’s why you’ve less than or equal. Otherwise if nums[l] < nums[r], this means m is in the second subarray, so the minimum value is either at m or somewhere left from it in the range [l, m], so set r = m. At some point you’ll either end up with l == r case which will break the loop or in more general and better case when nums[l] will just become less than nums[r].
Prime Course Trailer
Related Banners
Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription
Code :
class Solution {
public:
int findMin(vector< int>& nums) {
int l = 0, r = nums.size() - 1;
while (nums[l] > nums[r]) {
int m = (l + r) / 2;
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) {
final int m = (l + r) / 2;
if (nums[m] < nums[r])
r = m;
else
l = m + 1;
}
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)
if nums[m] > nums[r]:
l = m + 1
else:
r = m
return nums[l]
Get over 200+ course One Subscription
Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others
Login/Signup to comment