154. Find Minimum in Rotated Sorted Array II
The harder sibling of Find Minimum in Rotated Sorted Array: nums was again sorted ascending and then rotated some number of times (one rotation moves the last element to the front), but now values may repeat.
Return the minimum element of nums.
Duplicates poison the clean binary search: when the midpoint equals the window's right end you cannot tell which side hides the drop, and no algorithm can guarantee better than O(n) in the worst case (picture an array that is almost entirely one repeated value). The goal is a search that still runs in O(log n) on typical inputs while degrading gracefully to O(n) only when duplicates force it.
Example 1:
Input: nums = [1, 3, 5]
Output: 1
Explanation: Already in sorted order (rotated n times), so the first element is the minimum.
Example 2:
Input: nums = [2, 2, 2, 0, 1]
Output: 0
Explanation: [0, 1, 2, 2, 2] rotated 3 times. The repeated 2s surround the drop down to 0.
Constraints:
- 1 ≤ nums.length ≤ 5000
- -5000 ≤ nums[i] ≤ 5000
- nums was sorted in ascending order (duplicates allowed) and then rotated between 1 and n times
Hints:
Start from the duplicate-free version: compare nums[mid] with nums[hi] to decide which half must contain the drop.
The new case is nums[mid] == nums[hi]: the drop could be on either side, so you can't discard half. But nums[hi] itself is redundant — nums[mid] carries the same value — so shrinking the window by one (hi -= 1) is always safe.
That single-step shrink is exactly what makes the worst case O(n): an array like [1, 1, 1, 1] hits the equality branch every iteration.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: nums = [1, 3, 5]
Expected output: 1