Find Minimum in Rotated Sorted Array II
Given a sorted array nums that was rotated and may contain duplicates, find the minimum element.
- n == nums.length
- 1 <= n <= 5000
- -5000 <= nums[i] <= 5000
- nums is sorted and rotated between 1 and n times.
Intuition
Find minimum in rotated sorted array ii adds duplicates to the previous problem, and that single change breaks the logarithmic guarantee.
The earlier solution compared nums[mid] against nums[right] to decide which half held the minimum. With duplicates, a third case appears — the two can be equal — and equality carries no information:
- When nums[mid] == nums[right], the minimum could be on either side, so neither half can be discarded.
Consider [3, 3, 1, 3] and [3, 1, 3, 3]. Both have mid equal to right, yet the minimum sits in different halves. No comparison at those positions can tell them apart.
The standard resolution is to shrink the range by one:
right -= 1 when the two are equal. This is safe because nums[right] is duplicated at mid, so discarding it cannot remove the only copy of the minimum. It makes progress without risking the answer.
That step costs the logarithmic bound. An array like [1, 1, 1, 1, 1] reduces by one element per iteration, giving O(n) worst case — and this degradation is unavoidable, not an artefact of the implementation. Distinguishing those two arrays above genuinely requires examining more elements.
The other two branches are unchanged: nums[mid] > nums[right] moves left past mid, and nums[mid] < nums[right] keeps mid as a candidate. Average performance stays near O(log n) when duplicates are sparse.
Finding the minimum in a rotated sorted array is a binary search for the 'drop point'. Without duplicates, comparing mid to right always resolves the direction. With duplicates, the tell is nums[mid] == nums[right] — you handle it by shrinking the window linearly. The pattern appears whenever a sorted-but-shifted structure has repeats.
Approach
Before reading on: price up what the direct approach costs here, then ask what property lets you throw away half the range after one comparison. Aim for O(n) worst case, O(log n) average time and O(1) space.
Identify what duplicates break
The previous problem compared nums[mid] with nums[right]. Duplicates introduce a third case where they are equal, and equality reveals nothing about which half holds the minimum.
See the ambiguity concretely
[3, 3, 1, 3] and [3, 1, 3, 3] both have mid equal to right, yet their minima are in different halves. No comparison at those positions can distinguish them.
Keep the two decisive branches
nums[mid] > nums[right] means the minimum is further right, so left = mid + 1. nums[mid] < nums[right] keeps mid as a candidate with right = mid.
Shrink by one on equality
When the values are equal, set right -= 1. This is safe because nums[right] is duplicated at mid, so discarding it cannot remove the only copy of the minimum.
Accept the linear worst case
An array like [1, 1, 1, 1, 1] shrinks by one per iteration, giving O(n). This degradation is unavoidable, not an implementation flaw.
Cost of the search
O(log n) average when duplicates are sparse, degrading to O(n) worst case when they dominate. Space stays O(1).
Solution & live demo
Common pitfalls
Comparing nums[mid] with nums[left] instead of nums[right]
if nums[mid] > nums[left]:
left = mid + 1if nums[mid] > nums[right]:
left = mid + 1Comparing with nums[left] does not reliably locate the minimum. For [3, 1, 2], nums[mid]=1 < nums[left]=3 suggests the min is on the left, but the min is mid. Comparing with nums[right] correctly distinguishes the sorted right half.
Setting right = mid - 1 when nums[mid] < nums[right]
right = mid - 1
right = mid
When nums[mid] < nums[right], mid itself could be the minimum (it is the smallest in the right portion). Skipping it with mid - 1 can jump past the answer. For [4, 5, 1, 2, 3] with mid at index 2, nums[2]=1 is the answer.
Using left <= right loop condition instead of left < right
while left <= right:
while left < right:
The algorithm converges left and right to the same index. With <=, when left == right, the loop runs one extra time, and mid == left == right, causing an infinite loop because none of the branches change left or right.
Edge cases
[3,3,3,3]The == branch fires every iteration, shrinking right one by one. Eventually left == right, and the answer is any element — all are the same.
nums[mid] <= nums[right] always holds, so right converges to left at index 0 — the smallest element.
[2, 1]mid = 0, nums[0] > nums[1], so left = 1. Loop ends, nums[1] = 1 is correct.