Find Minimum in Rotated Sorted Array Solution In C++/Java/Python
Problem Description:
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.
Examples:
Input: nums = [3,4,5,1,2]
Output: 1
Explanation: The original array was [1,2,3,4,5] rotated 3 times.
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.
Input: nums = [11,13,15,17]
Output: 11
Explanation: The original array was [11,13,15,17], and it was rotated 4 times.
Constraints:
- n == nums.length
- 1 <= n <= 5000
- -5000 <= nums[i] <= 5000
- All the integers of nums are unique.
- Nums are sorted and rotated between 1 and n times.
In this problem, we are supposed to find the minimum element in a rotated sorted array.
For the time being, let's forget about solving this problem in O(logn) time complexity as mentioned in the problem statement. Rather we will approach it using a brute force method.
Let's see how to find the minimum element in a rotated sorted array...
Brute Force Approach
Intuition:
To address this problem, we can utilize a straightforward approach. The idea is to perform a linear search in a rotated sorted array; more precisely, we minimize the value throughout the entire array.
Find Minimum in Rotated Sorted Array Solution
To find the minimum in a rotated sorted array, let's start by visualizing an answer variable that will store the minimum element we encounter as we iterate through the array. We'll initialize our answer with the value of the first element of the array since it's a good starting point.
Next, we start iterating through the array from the second element (i.e., index 1). For each element at index i, we compare it with the value stored in our variable (which holds the minimum value found up to the previous element, i.e., index i-1). If the current element (nums[i]) is smaller than the value in our variable, we update the variable with this new, smaller value.
We continue this comparison for each element in the array, updating the variable whenever we find a smaller value. When we finish iterating through the array, the variable will hold the smallest element.
Finally, we return the value stored in this variable as the minimum element of the array.
Dry run
Input: nums = [7, 9, 11, 2, 4, 6]
Output: 2
Explanation: The original array was [2, 4, 6, 7, 9, 11] rotated 3 times.
Initialization:
- The variable ans is initialized with the first element of the array.
Iteration:
- The size of the array n is 6.
- We start iterating from the second element (index 1):
- First iteration (i = 1)
- nums[1] = 9
- Compare 9 with ans (7): ans remains 7
- Second iteration (i = 2):
- nums[2] = 11
- Compare 11 with ans (7): ans remains 7
- Third iteration (i = 3):
- nums[3] = 2
- Compare 2 with ans (7): ans is updated to 2
- Fourth iteration (i = 4):
- nums[4] = 4
- Compare 4 with ans (2): ans remains 2
- Fifth iteration (i = 5):
- nums[5] = 6
- Compare 6 with ans (2): ans remains 2.
- After completing all iterations, the variable ans holds the minimum element of the array, which is 2.
- The function returns ans.
Steps to write code
Step 1: Initialize the Minimum Variable:
- Start by initializing an ans variable to store the minimum element. Set it to the first element of the array.
Step 2: Iterate Through the Array:
- Use a loop to go through each element of the array starting from the second element.
Step 3: Compare and Update the Minimum Value:
- For each element, compare ans with the current value stored in the nums[i]. If the nums[i] is smaller, update the ans with this new value.
Step 4: Return the Minimum Value:
- After completing the iteration, return the value stored in the ans variable.
Brute Force in All Languages
Minimum in rotated sorted array C++
class Solution {
public:
// Function to find the minimum element in a sorted, rotated array
int findMin(vector<int>& nums) {
// Initialize the variable ans with the first element of the array
int ans = nums[0];
// Get the size of the array
int n = nums.size();
// Iterate through the array starting from the second element
for(int i = 1; i < n; ++i) {
// Compare and update the ans variable
ans = min(ans, nums[i]);
}
// Return the minimum value
return ans;
}
};Minimum in rotated sorted array java
class Solution {
// Function to find the minimum element in a sorted, rotated array
public int findMin(int[] nums) {
// Initialize the variable ans with the first element of the array
int ans = nums[0];
// Get the size of the array
int n = nums.length;
// Iterate through the array starting from the second element
for (int i = 1; i < n; ++i) {
// Compare and update the ans variable
ans = Math.min(ans, nums[i]);
}
// Return the minimum value
return ans;
}
}Minimum in rotated sorted array python
class Solution:
# Function to find the minimum element in a sorted, rotated array
def findMin(self, nums: list[int]) -> int:
# Initialize the variable ans with the first element of the array
ans = nums[0]
# Iterate through the array starting from the second element
for i in range(1, len(nums)):
# Compare and update the ans variable
ans = min(ans, nums[i])
# Return the minimum value
return ans
Minimum in rotated sorted array javascript
/**
* @param {number[]} nums
* @return {number}
*/
var findMin = function(nums) {
// Initialize the variable ans with the first element of the array
let ans = nums[0];
// Iterate through the array starting from the second element
for (let i = 1; i < nums.length; ++i) {
// Compare and update the ans variable
ans = Math.min(ans, nums[i]);
}
// Return the minimum value
return ans;
};Complexity Analysis of Find Minimum in Rotated Sorted Array Solution
Time Complexity: O(n)
Initialization of the Minimum Variable:
- Initializing the variable ans with the first element of the array takes constant time, O(1).
Getting the Size of the Array:
- Accessing the size of the array also takes constant time, O(1).
Iteration Through the Array:
- The loop runs from the second element (index 1) to the last element (index n-1). Since the array has n elements, this loop iterates n-1 times. This process takes linear time. O(n)
- Each iteration involves comparing the current element with the ans variable and potentially updating ans. These operations within the loop take constant time, O(1).
Returning the Result:
Returning the value of ans after completing the iteration takes constant time, O(1).
Hence total time complexity is O(n)
Space Complexity: O(1)
Auxiliary Space Complexity:
- Auxiliary space refers to the extra space or temporary space used by the algorithm during its execution, excluding the input data.
- In the provided code, we use a single variable ans to store the minimum element found during iteration. This variable takes constant space, O(1).
- The loop control variables (i and n) also take constant space, O(1).
Therefore, the auxiliary space complexity of the code is O(1).
Total Space Complexity:
- Total space complexity includes both the space used by the input data and the auxiliary space.
- The input array nums is given as input to the function, which takes up space O(n), where n is the number of elements in the array.
Total space complexity = Space used by input data + Auxiliary space complexity = O(n) + O(1) = O(n)
Is the brute force approach efficient?
The naive approach to find the minimum element in a sorted and rotated array has a time complexity of O(n), meaning it takes time proportional to the size of the input. We know that a system can perform 106(one million) operations in a second, an input size n of up to 5000 will be processed efficiently within a reasonable time.
However, in the problem statement, we are supposed to solve the problem in O(log n) time. Hence we have to optimize our solution further. Let's see how to do this...
Optimal Approach
Intuition:
We are given a sorted and rotated array. Let's first understand what a sorted array is.
A sorted array means the elements are arranged in ascending order.
For example: [1, 2, 3, 4, 5, 6]
In this array:
- The smallest element (1) is at index 0.
- Each subsequent element is greater than or equal to the previous one.
You can visualize this array as a line with a positive slope in the Cartesian plane. The elements increase as you move from left to right.
Rotate the array
Now, let's rotate the array. Rotating an array means shifting the elements to the left, where the elements at the beginning move to the end.
Let's see how this works:
- Original Sorted Array: [1, 2, 3, 4, 5, 6]
- Rotate Once:
- The element at index zero moves to the end
- The array becomes: [2, 3, 4, 5, 6, 1]
- Rotate TwiceTh
- the element initially at index 1 (2) moves to the end.
- The array becomes: [3, 4, 5, 6, 1, 2]
- Rotate Three Times:
- The element initially at index 2 (3) moves to the end.
- The array becomes: [4, 5, 6, 1, 2, 3]
Key Observations:
Adjacent Maximum and Minimum Elements:
- Observation: The maximum and minimum elements will always be adjacent if the array is rotated.
- Explanation: In a rotated sorted array, the maximum element is immediately followed by the minimum element. This occurs because rotation shifts the smallest element to the position immediately after the most significant aspect.
The division into Two Halves:
- Observation: The rotation divides the array into two halves. One half ranges from index 0 to the index of the pivot - 1, and the other half ranges from the index of the pivot to the end (n-1).
- Explanation: The pivot point is where the smallest element (minimum) resides. This point effectively splits the array into two subarrays: the first half (from the original start to just before the pivot) and the second half (from the pivot to the original end of the array). This division helps in narrowing down the search for the minimum element.
Comparison of End Elements:
- Observation: If the array is rotated, the element at index n-1 will be less than or equal to that at index 0.
- Explanation: Due to rotation, the largest element appears before the smallest element. This means the last element of the array (index n−1) is less than or equal to the first element (index 0). As a result, all elements in the first half of the array (before the smallest element) are greater than those in the second half (after the smallest element).
- Conclusion: This property is crucial for efficiently using binary search to find the minimum element in a rotated sorted array.
Now, if we pick any index in the array, it will either be in the first half or the second half of the rotated sorted array.
For example, consider the array: [4, 5, 6, 1, 2, 3].
If we pick index 3, the element at this index is 1.
Case 1: If the index we selected lies in the First Half
Example:
Let's say we pick index 1 in the array [4, 5, 6, 1, 2, 3]. The element at this index is 5, and it lies in the first half [4, 5, 6].
Conclusion:
Since this index is in the first half, we know that the minimum element (pivot) must be somewhere to the right of this index.
Why?... Because all elements in the first half are greater than those in the second half. The first half contains the larger numbers from the rotated array, while the smallest element is located in the second half.
Case 2: If the index we selected lies in the Second Half
Example:
Example:
Let's say we pick index 3 in the array [4, 5, 6, 1, 2, 3]. The element at this index is 1, and it lies in the second half [1, 2, 3].
Conclusion:
If the selected index is in the second half, there are two possibilities:
- The pivot is at the selected index – This means the element at this index is the smallest in the array. In our example, 1 is the smallest element, so it is the pivot.
- The pivot lies further to the left – If the element at this index isn’t the smallest, the pivot must be to the left of this index. Since the second half consists of increasing elements, once we enter this part of the array, the smallest element has already been encountered.
Now that we understand the structure of a sorted and rotated array, we can create a more efficient approach to find minimum in rotated sorted array without examining every element.
The key is to select an index, typically the middle of the array. By analyzing whether this middle element belongs to the first half or the second half, we can determine which side contains the pivot (the smallest element). This allows us to narrow down the search space significantly, leading to an optimal solution. Isn't it intuitive?
Find Minimum in Rotated SortedArray Algorithm.
To implement this approach, we use two pointers: low and high. The low pointer is initialized at index 0, while the high pointer starts at index n−1, covering the entire array.
In each step, we calculate the middle element (mid) of the current search space.
To determine whether the mid element is part of the first half or the second half of the rotated sorted array, we can use an important observation: All elements in the second half are smaller than all elements in the first half.
Initially, we focus on the last element of the array or the previous element within our current search space. Either option works effectively because this element is guaranteed to belong to the second half of the array, which contains the smallest element in that half. By comparing the value at mid with the last element of the array, we can determine which direction to proceed in our search.
If the value at mid is smaller than the value at high or the last element of the array, this indicates that the mid index lies in the second half of the array. The two values cannot be equal, as the array contains all unique elements.
This allows us to adjust our search space efficiently. If the mid-element lies in the first half, we continue searching to the right. If the mid element lies in the second half, we search to the left.
This method of narrowing the search space by half in each iteration is known as binary search. It’s an intuitive and highly effective approach to quickly finding the minimum in a rotated sorted array.
To know more about binary search refer to the article below...
Animation Explaination for Optimal Approach
Dry run
Input: nums = [7, 9, 11, 2, 4, 6]
Output: 2
Explanation: The original array was [2, 4, 6, 7, 9, 11] rotated 3 times.
Initial State:
- nums = [7, 9, 11, 2, 4, 6]
- n = nums.size() = 6
- l = 0
- h = 5 (last index of the array)
Iteration 1:
- Calculate mid: mid = (l + h) / 2 = (0 + 5) / 2 = 2
- nums[mid] = nums[2] = 11
- nums[h] = nums[5] = 6
- Compare nums[mid] with nums[h]:
- nums[mid] > nums[h] → 11 > 6 is true
- Update l: l = mid + 1 = 2 + 1 = 3
- State after iteration 1:
- l = 3
- h = 5
Iteration 2:
- Calculate mid: mid = (l + h) / 2 = (3 + 5) / 2 = 4
- nums[mid] = nums[4] = 4
- nums[h] = nums[5] = 6
- Compare nums[mid] with nums[h]:
- nums[mid] > nums[h] → 4 > 6 is false
- Update h: h = mid = 4
- State after iteration 2:
- l = 3
- h = 4
Iteration 3:
- Calculate mid: mid = (l + h) / 2 = (3 + 4) / 2 = 3
- nums[mid] = nums[3] = 2
- nums[h] = nums[4] = 4
- Compare nums[mid] with nums[h]:
- nums[mid] > nums[h] → 2 > 4 is false
- Update h: h = mid = 3
- State after iteration 3:
- l = 3
- h = 3
Termination:
- The while loop condition l < h is no longer true (since l = h = 3), so the loop terminates.
Result:
- Return nums[l]: return nums[3] = 2;
Steps to write code
Step 1: Initialize Variables:
- Start by defining the necessary variables to store the length of the array, the left pointer, and the right pointer.
- The left pointer should be initialized to the start of the array, and the right pointer should be initialized to the end of the array.
Step 2: Iterate Using a While Loop:
- Use a while loop that continues as long as the left pointer is less than the right pointer.
Step 3: Calculate the Middle Index:
- Within the loop, calculate the middle index using the formula (left + right) / 2.
Step 4: Compare Middle Element with Right Element:
- Compare the middle element with the right element of the array.
- If the middle element is greater than the right element, it means the minimum value is in the right half of the array. Update the left pointer to be middle + 1.
- Otherwise, if the middle element is less than or equal to the right element, it means the minimum value is in the left half of the array (including the middle element). Update the right pointer to be middle.
Step 5: Termination of Loop:
- The while loop will terminate when the left pointer is no longer less than the right pointer. At this point, the left pointer will be pointing to the minimum element in the array.
Step 6: Return the Minimum Element:
- Return the value at the position of the left pointer as the minimum element in the array.
Optimal Approach in All Languages
Minimum in rotated sorted array C++
class Solution {
public:
// Function to find the minimum element in a sorted, rotated array
int findMin(vector<int>& nums) {
// Get the size of the array
int n = nums.size();
// Initialize left and right pointers
int l = 0, h = n - 1;
// Use binary search to find the minimum element
while (l < h) {
// Calculate the middle index
int mid = (l + h) / 2;
// If middle element is greater than right element
if (nums[mid] > nums[h]) {
// Update left pointer to search the right half
l = mid + 1;
// If middle element is less than or equal to right element
} else {
// Update right pointer to search the left half
h = mid;
}
}
// Return the minimum element found
return nums[l];
}
};Minimum in rotated sorted array java
class Solution {
// Function to find the minimum element in a sorted, rotated array
public int findMin(int[] nums) {
// Get the size of the array
int n = nums.length;
// Initialize left and right pointers
int l = 0, h = n - 1;
// Use binary search to find the minimum element
while (l < h) {
// Calculate the middle index
int mid = (l + h) / 2;
// If middle element is greater than right element, update left pointer to search the right half
if (nums[mid] > nums[h]) {
l = mid + 1;
}
// If middle element is less than or equal to right element, update right pointer to search the left half
else {
h = mid;
}
}
// Return the minimum element found
return nums[l];
}
}Minimum in rotated sorted array python
class Solution:
# Function to find the minimum element in a sorted, rotated array
def findMin(self, nums: list[int]) -> int:
# Get the size of the array
n = len(nums)
# Initialize left and right pointers
l, h = 0, n - 1
# Use binary search to find the minimum element
while l < h:
# Calculate the middle index
mid = (l + h) // 2
# If middle element is greater than right element, update left pointer to search the right half
if nums[mid] > nums[h]:
l = mid + 1
# If middle element is less than or equal to right element, update right pointer to search the left half
else:
h = mid
# Return the minimum element found
return nums[l]Minimum in rotated sorted array javascript
/**
* @param {number[]} nums
* @return {number}
*/
// Function to find the minimum element in a sorted, rotated array
var findMin = function(nums) {
// Get the size of the array
let n = nums.length;
// Initialize left and right pointers
let l = 0, h = n - 1;
// Use binary search to find the minimum element
while (l < h) {
// Calculate the middle index
let mid = Math.floor((l + h) / 2);
// If middle element is greater than right element, update left pointer to search the right half
if (nums[mid] > nums[h]) {
l = mid + 1;
}
// If middle element is less than or equal to right element, update right pointer to search the left half
else {
h = mid;
}
}
// Return the minimum element found
return nums[l];
};Complexity Analysis of Find Minimum in Rotated Sorted Array Solution
Time Complexity: O(logn)
Initialization:
- Initializing the variables n, l, and h takes constant time, O(1).
While Loop:
- The while loop continues as long as l < h. In each iteration of the loop, the size of the search interval is effectively halved.
- This halving process is similar to a binary search with a logarithmic time complexity. O(logn)
n → n/2 → n/4 → n/8 → ... → 1
Calculation of mid:
- Calculating the middle index mid = (l + h) / 2 takes constant time, O(1), in each iteration.
Comparison and Update:
- Comparing nums[mid] with nums[h] and updating the pointers l or h both take constant time, O(1), in each iteration.
Since the while loop halves the search interval in each iteration, the number of iterations required is logarithmic with the size of the input array.
Space Complexity: O(1)
Auxiliary Space Complexity:
- Auxiliary space refers to the extra space or temporary space used by the algorithm during its execution, excluding the input data.
- In the provided code, we use a few variables to store indices and lengths: n, l, h, and mid. Each of these variables takes constant space, O(1).
Therefore, the auxiliary space complexity is O(1).
Total Space Complexity:
- Total space complexity includes both the space used by the input data and the auxiliary space.
- The input array nums takes up space O(n), where n is the number of elements in the array.
- Total space complexity = Space used by input data + Auxiliary space complexity = O(n) + O(1) = O(n)
Similar Problems
Now we have successfully tackled this problem, let these similar problems:-
An integer array of nums is Ansorted in ascending order (with distinct values).
Before being passed to your function, nums is possibly rotated at an unknown pivot index k (1 <= k < nums.length) such that the resulting array is [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]] (0-indexed). For example, [0,1,2,4,5,6,7] might be rotated at pivot index three and become [4,5,6,7,0,1,2].
Given the array nums after the possible rotation and an integer target, return the index of target if it is in nums, or -1 if it is not in nums.
You must write an algorithm with O(log n) runtime complexity.
Suppose an array of length n sorted in ascending order is rotated between 1 and n times. For example, the array nums = [0,1,4,4,5,6,7] might become:
- [4,5,6,7,0,1,4] if it was rotated 4 times.
- [0,1,4,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 that may contain duplicates, return the minimum element of this array.
You must decrease the overall operation steps as much as possible.