https://leetcode.com/problems/find-minimum-in-rotated-sorted-array-ii/description/
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: 1
Example 2:
Input: nums = [2,2,2,0,1]
Output: 0
Constraints:
n == nums.length
1 <= n <= 5000
-5000 <= nums[i] <= 5000
nums is sorted and rotated between 1 and n times.
package LeetCode.binarySearch;
public class LT154_SearchInRotatedSortedArray_duplicates {
public static void main(String[] args) {
int[] arr = {1};
System.out.println(findMin(arr));
// TC: O(log n) in best/average case, O(n) in worst case due to duplicates
// SC: O(1)
}
public static int findMin(int[] nums) {
int low = 0, high = nums.length - 1; // SC: O(1), initializing variables
int min = Integer.MAX_VALUE; // SC: O(1), auxiliary variable to track min
while (low <= high) { // TC: O(log n) best/avg, O(n) worst when duplicates reduce one by one
int mid = low + (high - low) / 2; // SC: O(1)
if (nums[low] < nums[high]) { // TC: O(1), check if already sorted
return Integer.min(nums[low], min); // SC: O(1)
}
if (nums[low] == nums[mid] && nums[mid] == nums[high]) { // TC: O(1)
min = Integer.min(nums[low], min); // SC: O(1)
low++; // TC: O(1)
high--; // TC: O(1)
}
// left half is sorted
else if (nums[low] <= nums[mid]) { // TC: O(1)
min = Integer.min(nums[low], min); // SC: O(1)
low = mid + 1; // TC: O(1)
} else {
min = Integer.min(nums[mid], min); // SC: O(1)
high = mid - 1; // TC: O(1)
}
}
return min; // SC: O(1)
}
}
Here’s the Time and Space Complexity of the findMin function in a clear table format:
| Case | Time Complexity | Space Complexity |
|---|---|---|
| Best | O(1) | O(1) |
| Average | O(log n) | O(1) |
| Worst | O(n) | O(1) |
Explanation:
-
Best Case: The array is already sorted (
nums[low] < nums[high]). -
Average Case: Standard binary search logic with occasional duplicates.
-
Worst Case: All or many elements are duplicates, causing the loop to degrade into linear time.
