Given a rotated sorted array nums that may contain duplicate values, find the minimum element in the array. Return that minimum value.
A rotated sorted array means the array was originally sorted in non-decreasing order and then rotated at some pivot.
Prerequisite: Find minimum in rotated sorted array
Example 1
Input: nums = [1, 3, 5]
Output: 1
Explanation: The array is already sorted, so the first element is the minimum.
Example 2
Input: nums = [2, 2, 2, 0, 1]
Output: 0
Explanation: Even though many values are repeated, 0 is the smallest element in the array.
Brute Force Approach
The most direct thought is to ignore the rotation and duplicates completely. Just scan the whole array and keep track of the smallest value seen so far. This always works because the minimum value stays the minimum no matter how the array was rotated.
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 value gets checked once.
If the current value is smaller than the stored minimum, update the minimum because a new smaller minimum is found.
After the full array is processed, return the stored minimum.
Dry Run
Brute
Solution
#include <bits/stdc++.h>using namespace std;class Solution {public: /* Returns the minimum element from the rotated sorted array. */ int findMin(vector<int>& nums) { // This stores the smallest value found so far. int minimum = nums[0]; // Check every element to see whether a smaller value exists. for (int i = 1; i < (int)nums.size(); i++) { // Update the answer because a smaller value is found here. if (nums[i] < minimum) { minimum = nums[i]; } } return minimum; }};// Driver code startsint main() { vector<int> nums = {2, 2, 2, 0, 1}; Solution obj; cout << obj.findMin(nums) << endl; return 0;}Complexity Analysis
Time Complexity: O(N), N is the length of array, because every element may need to be checked.
Space Complexity: O(1), because only one extra variable is used.
Optimal Approach
The useful idea from version 1 still remains: compare the middle element with the right side and decide where the minimum can be.
If nums[mid] < nums[high], the right part is sorted in a way that means the minimum is at mid or on the left side.
If nums[mid] > nums[high], the minimum must be on the right side.
The tricky case appears when nums[mid] == nums[high]. At that moment, duplicates hide the real structure. The comparison gives no direction because both sides may still contain the minimum.
So the safe move is to reduce high by 1 and continue. That removes one duplicate from consideration without losing the minimum.
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.Find the middle index using
mid = low + (high - low) / 2.If
nums[mid] < nums[high], movehightomidbecause the minimum is atmidor on the left side.If
nums[mid] > nums[high], movelowtomid + 1because the minimum must be on the right side.Otherwise, reduce
highby1because duplicate values prevent a clear decision at that step.When the loop ends, return
nums[low]because both pointers meet at the minimum element.
Key Points
When
nums[mid] == nums[high], the search cannot safely choose a half, so shrinking the range by one is the correct step.In the worst case, such as many repeated values, the time complexity can degrade from O(log2 N) to O(N).
Dry Run
Optimal
Solution
#include <bits/stdc++.h>using namespace std;class Solution {public: /* Returns the minimum element from the rotated sorted array. */ int findMin(vector<int>& nums) { // Left boundary of the current search range. int low = 0; // Right boundary of the current search range. int high = (int)nums.size() - 1; // Keep shrinking the range until only the minimum position remains. while (low < high) { // Calculate the middle index safely. int mid = low + (high - low) / 2; // The minimum is at mid or on the left side here. if (nums[mid] < nums[high]) { high = mid; } // The minimum must be on the right side here. else if (nums[mid] > nums[high]) { low = mid + 1; } // Duplicates hide the direction, so remove one value from the right. else { high--; } } return nums[low]; }};// Driver code startsint main() { vector<int> nums = {2, 2, 2, 0, 1}; Solution obj; cout << obj.findMin(nums) << endl; return 0;}Complexity Analysis
Time Complexity: Average case is close to O(log2 N), but the worst case becomes O(N) because duplicates may force the search range to shrink one step at a time. N is the length of array.
Space Complexity: O(1), because only a few variables are used.
Interview follow-up Questions
When all elements are unique, comparing nums[mid] and nums[high] always helps decide which half contains the minimum, allowing binary search to work in O(log2 N). With duplicates, nums[mid] can equal nums[high], making it impossible to determine the correct half. In that case, we safely reduce high by 1. If this happens repeatedly, the worst-case time complexity becomes O(N).
Be the first to add a comment.