Find Minimum in Rotated Sorted Array II
HardPrompt
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 rotated4times.[0,1,4,4,5,6,7]if it was rotated7times.
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.
Example 1:
Input: nums = [1,3,5]
Output: 1Example 2:
Input: nums = [2,2,2,0,1]
Output: 0
Constraints:
n == nums.length1 <= n <= 5000-5000 <= nums[i] <= 5000numsis sorted and rotated between1andntimes.
Follow up: This problem is similar to Find Minimum in Rotated Sorted Array, but nums may contain duplicates. Would this affect the runtime complexity? How and why?
Approaches
2 approaches with complexity analysis and trade-offs.
This is a straightforward brute-force approach. We can find the minimum element by simply iterating through the entire array and keeping track of the smallest value encountered.
Algorithm
- Initialize
minimumtonums[0]. - Loop through the array from the second element (
i = 1) to the end. - Inside the loop, if
nums[i]is less thanminimum, updateminimum = nums[i]. - After the loop, return
minimum.
Walkthrough
The algorithm works by initializing a variable, say minimum, with the value of the first element of the array. It then traverses the array from the second element to the end. For each element, it compares it with the current minimum. If the current element is smaller, minimum is updated. After checking all elements, the minimum variable will hold the smallest value in the array. This approach does not take advantage of the fact that the array is a rotated sorted array, but it is guaranteed to be correct.
class Solution { public int findMin(int[] nums) { if (nums == null || nums.length == 0) { return -1; // Based on constraints, this won't be reached. } int minimum = nums[0]; for (int i = 1; i < nums.length; i++) { if (nums[i] < minimum) { minimum = nums[i]; } } return minimum; }}Complexity
Time
O(n)
Space
O(1)
Trade-offs
Pros
Very simple to understand and implement.
Works for any array, not just rotated sorted ones.
Cons
Inefficient as it doesn't use the properties of the input array.
Has a time complexity of O(n), which can be improved upon.
A more optimized approach is to adapt the binary search algorithm. The standard binary search works on sorted arrays, and we can modify it to handle the rotation and duplicates. The core idea is to intelligently shrink the search space based on comparisons between the middle element and the boundaries.
Algorithm
- Initialize two pointers,
left = 0andright = nums.length - 1. - Loop while
left < right. - Calculate the middle index:
mid = left + (right - left) / 2. - If
nums[mid] < nums[right], it means the right part is sorted and the minimum is in the left part (includingmid). So, setright = mid. - If
nums[mid] > nums[right], it means the pivot is in the right part. So, setleft = mid + 1. - If
nums[mid] == nums[right], we cannot determine the location of the minimum. To be safe, we reduce the search space by one element from the right:right--. - When the loop ends,
leftandrightwill point to the same index, which holds the minimum element. Returnnums[left].
Walkthrough
We use two pointers, left and right, to define our search space, initially covering the whole array. We iterate as long as left < right. In each step, we find the middle element mid. The main logic revolves around comparing nums[mid] with nums[right]:
- If
nums[mid] < nums[right]: This implies that the segment frommidtorightis sorted. The minimum element cannot be in the(mid, right]range becausenums[mid]is smaller thannums[right]. Therefore, the minimum must be in the[left, mid]range. We updateright = mid. - If
nums[mid] > nums[right]: This indicates that the rotation point (and thus the minimum element) is in the right half of the current search space. The segment[left, mid]is sorted and all its elements are greater thannums[right]. So, the minimum must be in[mid + 1, right]. We updateleft = mid + 1. - If
nums[mid] == nums[right]: This is the tricky case introduced by duplicates. We cannot be certain which half contains the minimum. For instance, in[3, 1, 3, 3]and[3, 3, 1, 3],nums[mid]can be equal tonums[right], but the minimum is in different halves relative tomid. In this situation, we can't discard half of the search space. However, we can safely discard the element at therightpointer by decrementingright. This is safe because even ifnums[right]was the minimum,nums[mid]has the same value, so we are not losing the minimum value from our search space. This step may degrade the performance to linear time in the worst case (e.g., an array of all same elements), but on average, it's much faster.
The loop continues until left and right converge (left == right). The element at this index is the minimum.
class Solution { public int findMin(int[] nums) { int left = 0; int right = nums.length - 1; while (left < right) { int mid = left + (right - left) / 2; if (nums[mid] < nums[right]) { right = mid; } else if (nums[mid] > nums[right]) { left = mid + 1; } else { // nums[mid] == nums[right] right--; } } return nums[left]; }}Complexity
Time
O(log n) on average, O(n) in the worst case
Space
O(1)
Trade-offs
Pros
Significantly more efficient than linear scan on average, with a time complexity of O(log n).
Utilizes the sorted and rotated nature of the array.
Cons
The worst-case time complexity degrades to O(n) when many duplicates are present, making it no better than a linear scan in those specific scenarios.
The logic is more complex to implement and reason about compared to a simple loop.
Solutions
Solution
class Solution {public int findMin(int[] nums) { int left = 0, right = nums.length - 1; while (left < right) { int mid = (left + right) >> 1; if (nums[mid] > nums[right]) { left = mid + 1; } else if (nums[mid] < nums[right]) { right = mid; } else { --right; } } return nums[left]; }}/** * @param {number[]} nums * @return {number} */ var findMin = function ( nums,) { let left = 0, right = nums.length - 1; while (left < right) { const mid = (left + right) >> 1; if (nums[mid] > nums[right]) { left = mid + 1; } else if (nums[mid] < nums[right]) { right = mid; } else { --right; } } return nums[left];};class Solution {public: int findMin(vector<int> &nums) { int left = 0, right = nums.size() - 1; while (left < right) { int mid = (left + right) >> 1; if (nums[mid] > nums[right]) left = mid + 1; else if (nums[mid] < nums[right]) right = mid; else --right; } return nums[left]; }};class Solution: def findMin(self, nums: List[int]) -> int: left, right = 0, len(nums) - 1 while left < right: mid = (left + right) >> 1 if nums[mid] > nums[right]: left = mid + 1 elif nums[mid] < nums[right]: right = mid else: right -= 1 return nums[left]Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.