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.
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]; }}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.