Find Minimum in Rotated and Sorted Array
Program for Finding Minimum in a Rotated Sorted Array Problem
You are given a sorted array that has been rotated between 1 and n times. For example:
- If the array [1,2,3,4,5,6] is rotated 4 times, it becomes [3,4,5,6,1,2].
- If rotated 6 times, it goes back to [1,2,3,4,5,6].
Your task is to find the smallest element in this rotated array. The elements in the array are unique.
While finding the minimum in O(n) time is easy, you need to write an algorithm that works in O(logn) time.
Output: 1
Output: 0
Output: 4
Constraints:
- 1 <= nums.length <= 1000
- -1000 <= nums[i] <= 1000
Program for Finding Minimum in a Rotated Sorted Array Solution
Recommendation for Time and Space Complexity – You should aim for a solution with O(logn) time and O(1) space, where n is the size of the input array.
Hints for solving problems
Hint 1 :
A brute force solution would be to do a linear search on the array to find the minimum element. This would be an O(n) solution. Can you think of a better way? Maybe an efficient searching algorithm is helpful.
Hint 2 :
Given that the array is rotated after sorting, elements from the right end are moved to the left end one by one. This creates two parts of a sorted array, separated by a deflection point caused by the rotation. For example, consider the array [3, 4, 1, 2]. Here, the array is rotated twice, resulting in two sorted segments: [3, 4] and [1, 2]. And the minimum element will be the first element of the right segment. Can you do a binary search to find this cut?
Hint 3 :
We perform a binary search on the array with pointers l and r, which belong to two different sorted segments. For example, in [3, 4, 5, 6, 1, 2, 3], l = 0, r = 6, and mid = 3. At least two of l, mid, and r will always be in the same sorted segment. Can you find conditions to eliminate one half and continue the binary search? Perhaps analyzing all possible conditions for l, mid, and r would help.
Hint 4 :
There will be two conditions where l and mid will be in left sorted segment or mid and r will be in right sorted segement. If l and mid in sorted segement, then nums[l] < nums[mid] and the minimum element will be in the right part. If mid and r in sorted segment, then nums[m] < nums[r] and the minimum element will be in the left part. After the binary search we end up finding the minimum element.
There are mainly 3 approach to solve this problem-
- Brute Force Method
- Binary Search Method
- Binary Search Method(Lower Bound)
1. Brute Force Method
Iterate through the entire array to find the minimum element by comparing each element, resulting in an O(n) solution.
- Time complexity: O(n)
- Space complexity: O(1)
Code
class Solution {
public:
int findMin(vector<int>& nums) {
return *min_element(nums.begin(), nums.end());
}
};
public class Solution {
public int findMin(int[] nums) {
return Arrays.stream(nums).min().getAsInt();
}
}
class Solution:
def findMin(self, nums: List[int]) -> int:
return min(nums)
class Solution {
/**
* @param {number[]} nums
* @return {number}
*/
findMin(nums) {
return Math.min(...nums);
}
}
2. Binary Search Method
Use binary search to narrow down the search space by checking if the middle element lies in the rotated part, giving an O(logn) solution.
- Time complexity: O(log 1)
- Space complexity: O(1)
Code
class Solution {
public:
int findMin(vector<int> &nums) {
int res = nums[0];
int l = 0;
int r = nums.size() - 1;
while (l <= r) {
if (nums[l] < nums[r]) { res = min(res, nums[l]); break; } int m = l + (r - l) / 2; res = min(res, nums[m]); if (nums[m] >= nums[l]) {
l = m + 1;
} else {
r = m - 1;
}
}
return res;
}
};
public class Solution {
public int findMin(int[] nums) {
int l = 0;
int r = nums.length - 1;
int res = nums[0];
while (l <= r) {
if (nums[l] < nums[r]) {
res = Math.min(res, nums[l]);
break;
}
int m = l + (r - l) / 2;
res = Math.min(res, nums[m]);
if (nums[m] >= nums[l]) {
l = m + 1;
} else {
r = m - 1;
}
}
return res;
}
}
class Solution:
def findMin(self, nums: List[int]) -> int:
res = nums[0]
l, r = 0, len(nums) - 1
while l <= r:
if nums[l] < nums[r]:
res = min(res, nums[l])
break
m = (l + r) // 2
res = min(res, nums[m])
if nums[m] >= nums[l]:
l = m + 1
else:
r = m - 1
return res
class Solution {
/**
* @param {number[]} nums
* @return {number}
*/
findMin(nums) {
let l = 0;
let r = nums.length - 1;
let res = nums[0];
while (l <= r) {
if (nums[l] <= nums[r]) {
res = Math.min(res, nums[l]);
break;
}
let m = l + Math.floor((r - l) / 2);
res = Math.min(res, nums[m]);
if (nums[m] >= nums[l]) {
l = m + 1;
} else {
r = m - 1;
}
}
return res;
}
}
3. Binary Search Method(Lower Bound)
Apply a binary search to find the pivot point where the sorted order breaks, effectively finding the smallest element in O(logn) time.
- Time complexity: O(log n)
- Space complexity: O(1)
Code
class Solution {
public:
int findMin(vector<int>& nums) {
int l = 0, r = nums.size() - 1;
while (l < r) {
int m = l + (r - l) / 2;
if (nums[m] < nums[r]) {
r = m;
} else {
l = m + 1;
}
}
return nums[l];
}
};
public 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[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) // 2
if nums[m] < nums[r]:
r = m
else:
l = m + 1
return nums[l]
class Solution {
/**
* @param {number[]} nums
* @return {number}
*/
findMin(nums) {
let l = 0, r = nums.length - 1;
while (l < r) {
let m = l + Math.floor((r - l) / 2);
if (nums[m] < nums[r]) {
r = m;
} else {
l = m + 1;
}
}
return nums[l];
}
}
