Problem Statement
Given an integer array nums of size N, sorted in ascending order with distinct values, and then rotated an unknown number of times (between 1 and N), find the minimum element in the array.
Examples
Example 1:
Input: nums = [4, 5, 6, 7, 0, 1, 2]
Output: 0
Explanation: In this array element 0 is the minimum.Example 2:
Input: nums = [3, 4, 5, 1, 2]
Output: 1
Explanation: In this array element 1 is the minimum.Example 3:
Input: nums = [4, 5, 6, 7, -7, 0, 1, 2]
Output: -7
Explanation: In this array element -7 is the minimum.Different Approaches
1️⃣ Linear Search
Intuition:
The idea here is to use simple linear search to find out the minimum element among the array elements.
Approach:
- Begin by initializing mini to INT_MAX, which is the maximum possible value for integers. This ensures that any element in the array will be smaller than mini initially.
- Use a for loop to iterate through each element in the array. For each element, update `mini` using the min function. This function compares the current value of mini with the current element and assigns the smaller value back to `mini`. This effectively finds the smallest element encountered so far in the array.
- Continue iterating until all elements of the array have been processed. Each iteration ensures that `mini` retains the smallest value found among the elements seen so far. Return this value as the result of the function.
Code:
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
// Function to find minimum element in a vector
int findMin(vector<int>& arr) {
int n = arr.size();
// Initialize mini to maximum integer value
int mini = INT_MAX;
for (int i = 0; i < n; i++) {
/* Update mini with the
smaller of mini and arr[i]*/
mini = min(mini, arr[i]);
}
// Return the minimum element found
return mini;
}
};
int main() {
vector<int> arr = {4, 5, 6, 7, 0, 1, 2, 3};
// Create an object of the Solution class
Solution sol;
int ans = sol.findMin(arr);
//Print the result
cout << "The minimum element is: " << ans << "\n";
return 0;
}
Complexity Analysis:
- Time Complexity:
O(N), whereNis size of the array. As the array is being traversed only once using a single loop. - Space Complexity:
O(1), As no additional space is used.
2️⃣ Binary Search
Intuition:
As the given array is sorted and then rotated, we can optimize the brute-force solution by applying the binary search algorithm. In any sorted array, the minimum element is located at the very first index. This observation allows us to reduce the search space by half in each iteration. The task is to identify the sorted half of the array, store its minimum element (which is the first element of this half), and then eliminate this half from our search space.
Approach:
- First, initialize few variables: low to 0 and high to sizeOfArray - 1, which represent the indices of the array arr that define the current search range, ans to Integer's MAX_VALUE, which ensures that any element in the array will be smaller than ans initially.
- Use a while loop to continue searching while low is less than or equal to high. This ensures that the search space is valid and non-empty. Compute the midpoint mid of the current search range using mid = (low + high) / 2 or mid = low + (high-low)/2.
- Compare element at (low) with element at (mid). If element at (low) is less than or equal to element at (mid), then the left part from low to mid is sorted:
- Update ans with the minimum of its current value and element at (low). This step ensures that ans always holds the smallest element encountered in the sorted part of the array.
- Move the low pointer to mid + 1 to search in the right part of the array, as the minimum element cannot be in the left part (which is already sorted).
- If the left part is not sorted (element at (low) is greater than element at (mid)), then the right part from mid to high is sorted:
- Update
answith the minimum of its current value and element at (mid). This ensures ans contains the smallest element encountered in the sorted part of the array. - Move the high pointer to mid - 1 to search in the left part of the array, as the minimum element cannot be in the right part (which is already sorted).
- Update
- Once the loop completes,
answill contain the smallest element found in the rotated sorted array. Returnansas the minimum element in the rotated sorted array.
Dry Run:
Initialization:
Left = 0
Right = 6
minimum = INT_MAX
+-----+-----+-----+-----+-----+-----+-----+
arr = | 4 | 5 | 6 | 7 | 0 | 1 | 2 |
+-----+-----+-----+-----+-----+-----+-----+
0 1 2 3 4 5 6First Iteration:
Left = 0
Right = 6
Mid = Left + (Right - Left) / 2
= 0 + (6 - 0) / 2 = 3
= 3
minimum = INT_MAX
+-----+-----+-----+-----+-----+-----+-----+
arr = | 4 | 5 | 6 | 7 | 0 | 1 | 2 |
+-----+-----+-----+-----+-----+-----+-----+
0 1 2 3 4 5 6
^ ^ ^
| | |
Left Mid Right
Check which side is sorted
If, arr[Left] <= arr[Mid]
4 <= 7
True
As we know that minimum element would be at
extreme left position of sorted arry, so set
the minimum to min of itself and arr[Left]
minimum = min(minimum, arr[Left])
minimum = 4
and Now we have to go the other part of the
array
So GO RIGHT
Left = mid + 1
Left = 3 + 1Second Iteration:
Left = 4
Right = 6
Mid = Left + (Right - Left) / 2
= 4 + (6 - 4) / 2 = 4 + 1
= 5
minimum = 4
+-----+-----+-----+-----+-----+-----+-----+
arr = | 4 | 5 | 6 | 7 | 0 | 1 | 2 |
+-----+-----+-----+-----+-----+-----+-----+
0 1 2 3 4 5 6
^ ^ ^
| | |
Left Mid Right
Check which side is sorted
If, arr[Left] <= arr[Mid]
0 <= 1
True
As we know that minimum element would be at
extreme left position of sorted arry, so set
the minimum to min of itself and arr[Left]
minimum = min(minimum, arr[Left])
minimum = min(4, 0)
minimum = 0
and Now we have to go the other part of the
array
So GO RIGHT
Left = mid + 1
Left = 5 + 1 = 6Third Iteration:
Left = 6
Right = 6
Mid = Left + (Right - Left) / 2
= 6 + (6 - 6) / 2 = 6 + 0
= 6
minimum = 0
+-----+-----+-----+-----+-----+-----+-----+
arr = | 4 | 5 | 6 | 7 | 0 | 1 | 2 |
+-----+-----+-----+-----+-----+-----+-----+
0 1 2 3 4 5 6
^
|
Right
Left
Mid
Check which side is sorted
If, arr[Left] <= arr[Mid]
2 <= 2
True
As we know that minimum element would be at
extreme left position of sorted arry, so set
the minimum to min of itself and arr[Left]
minimum = min(minimum, arr[Left])
minimum = min(0, 2)
minimum = 0
and Now we have to go the other part of the
array
So GO RIGHT
Left = mid + 1
Left = 6 + 1 = 7Loop Termination:
Left = 7
Right = 6
minimum = 0
As, the Left as Crosses the Right so,
the Loop would terminate here and
return minimum which is 0.
+-----+-----+-----+-----+-----+-----+-----+
arr = | 4 | 5 | 6 | 7 | 0 | 1 | 2 |
+-----+-----+-----+-----+-----+-----+-----+
0 1 2 3 4 5 6 7
^ ^
| |
Right Left
Code:
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
/* Function to find minimum element
in a rotated sorted array */
int findMin(vector<int>& arr) {
// Initialize low and high indices
int low = 0, high = arr.size() - 1;
// Initialize ans to maximum integer value
int ans = INT_MAX;
while (low <= high) {
int mid = low + (high - low) / 2;
// Check if left part is sorted
if (arr[low] <= arr[mid]) {
/* Update ans with minimum
of ans and arr[low] */
ans = min(ans, arr[low]);
// Move to the right part
low = mid + 1;
}
else {
/* Update ans with minimum
of ans and arr[mid] */
ans = min(ans, arr[mid]);
// Move to the left part
high = mid - 1;
}
}
// Return the minimum element found
return ans;
}
};
int main() {
vector<int> arr = {4, 5, 6, 7, 0, 1, 2, 3};
// Create an object of the Solution class
Solution sol;
int ans = sol.findMin(arr);
// Print the result
cout << "The minimum element is: " << ans << "\n";
return 0;
}If the array contains Duplicates:
class Solution {
public:
int findMin(vector<int>& nums) {
int left = 0; // Initialize the left pointer
int right = nums.size() - 1; // Initialize the right pointer
// If the array contains only one element, return that element
if (nums.size() == 1) {
return nums[0];
}
int minimum = INT_MAX; // Initialize minimum to a large value
// Binary search loop
while (left <= right) {
int mid = left + (right - left) / 2; // Calculate the middle index
// If nums[left], nums[mid], and nums[right] are equal, skip duplicates
if (nums[left] == nums[mid] && nums[mid] == nums[right]) {
minimum = min(minimum, nums[left]); // Update the minimum value
left++; // Increment left pointer
right--; // Decrement right pointer
continue; // Skip further checks for this iteration
}
// Check which part of the array is sorted
if (nums[left] <= nums[mid]) {
// If the left part is sorted
minimum = min(minimum, nums[left]); // Update the minimum value with nums[left]
left = mid + 1; // Move to the right part for exploration
} else {
// If the right part is sorted
minimum = min(minimum, nums[mid]); // Update the minimum value with nums[mid]
right = mid - 1; // Move to the left part for exploration
}
}
// Return the minimum value found
return minimum;
}
};
This code handles the duplicates in the array.
Complexity Analysis:
- Time Complexity:
O(log(N)), whereNis size of the array. Because binary search is being used. - Space Complexity:
O(1)As no additional space is used.