Given a sorted array of distinct integers that has been left rotated some number of times, find the minimum element in the array.
Return that minimum value.
Example 1
Input: arr = [3, 4, 5, 1, 2]
Output: 1
Explanation: The minimum element is 1 .
Example 2
Input: arr = [11, 13, 15, 17]
Output: 11
Explanation: The minimum element is 11 .
Brute Force Approach
The most direct thought is simple: the minimum element is just the smallest value in the array. So instead of worrying about rotation, just scan every element and keep track of the smallest one found so far. This works because rotation changes positions, but it does not change the values present in the array.
Algorithm
Start by storing the first element as the current minimum because it is the only value seen at the beginning.
Traverse the array from left to right so every element gets checked once.
If the current element is smaller than the stored minimum, update the minimum because a better answer has been found.
After the full array is processed, return the stored minimum.
Dry Run
Find Minimum in Rotated Sorted Array
Solution
#include <bits/stdc++.h>using namespace std;class Solution {public: /* Returns the minimum element from the rotated sorted array. */ int findMin(vector<int>& arr) { // This stores the smallest value found so far. int minimum = arr[0]; // Check every element to see whether a smaller value exists. for (int i = 1; i < (int)arr.size(); i++) { // Update the answer because a smaller value is found here. if (arr[i] < minimum) { minimum = arr[i]; } } return minimum; }};// Driver code startsint main() { vector<int> arr = {3, 4, 5, 1, 2}; Solution obj; cout << obj.findMin(arr) << endl; return 0;}Complexity Analysis
Time Complexity: O(N), N is the length of array, because every element may need to be visited once.
Space Complexity: O(1), because only one extra variable is used.
Optimal Approach
The important observation is that even after rotation, one half of the current range is still properly sorted. If the current range from low to high is already sorted, then the first element of that range is automatically the minimum. If the range is not sorted, the break point must be inside it.
Now the useful comparison comes from arr[mid] and arr[high]. If arr[low] <= arr[mid], the middle element belongs to the left larger part, so the minimum must be somewhere on the right side.
Otherwise, the minimum is at mid or on the left side, so that part must be kept in the search range. That is why binary search fits this problem so nicely. Each comparison tells which half can be removed safely.
Algorithm
Start with two pointers,
low = 0andhigh = N - 1, because the minimum can be anywhere in the array.Keep searching while
low < high, because once both pointers meet, that position itself gives the answer.First check whether
arr[low] <= arr[high]. This matters because an already sorted range has its minimum at the first position.Find the middle index using
mid = low + (high - low) / 2so the current range can be split into two parts.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 fromlow to midis 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
lowpointer tomid + 1to 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 tohighis sorted:Update ans with 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 - 1to search in the left part of the array, as the minimum element cannot be in the right part (which is already sorted).
When the loop ends, return
arr[low]because both pointers meet exactly at the minimum element.
Dry Run
Optimal
Solution
#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) / 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; }Complexity Analysis
Time Complexity: O(log2 N), N is the length of array, because half of the current range is discarded in each step.
Space Complexity: O(1), because only a few variables are used.
Interview follow-up Questions
Then the array is already sorted, so the first element is the minimum.
Be the first to add a comment.