Back to main article
LC 154 First True Hard

Find Minimum in Rotated Sorted Array II

LC 153 with duplicates added. One extra line of code — but understanding why it's needed reveals a fundamental truth about binary search and ambiguity.

Problem

What are we solving?

Problem Statement

This is the same as LC 153, but the array may contain duplicate elements. Given the rotated array nums, return the minimum element. You must minimise the number of operations overall.

Example 1
Input:nums = [1, 3, 5]
Output:1
Example 2 — with duplicates
Input:nums = [2, 2, 2, 0, 1]
Output:0
Example 3 — the tricky case
Input:nums = [3, 3, 1, 3, 3]
Output:1
Intuition

Why duplicates break the LC 153 logic

In LC 153, the condition nums[mid] <= nums[last] unambiguously tells us which segment mid is in. Duplicates destroy this guarantee.

Consider: [3, 3, 1, 3, 3] where last = 3. When nums[mid] == nums[last] == 3, we genuinely cannot tell whether mid is in the upper segment (before the pivot) or the lower segment (after the pivot).

Ambiguous case: [3, 3, 1, 3, 3] · last = 3
i=03
i=13
i=21
i=33
i=43
Index 0,1 are in the upper segment. Index 3,4 are in the lower segment. Both equal 3 = last. We can't tell them apart using the LC 153 condition.

When nums[mid] == nums[last], the element could be on either side of the pivot. The solution: shrink the right boundary by one and try again. We safely eliminate one candidate without losing the minimum.

The fix — one extra line

The entire modification fits in a single else if branch:

Walkthrough: [3, 3, 1, 3, 3]
condition: nums[mid] <= nums[last] (with tie-breaking)
1
left=0, right=4 → mid=2, nums[2]=1, last=3

1 <= 3? Yes → TRUE. Save boundary=2, search left: right=1.

2
left=0, right=1 → mid=0, nums[0]=3, last=3

3 == 3 → AMBIGUOUS. Shrink right: right=right-1=0. No boundary update.

3
left=0, right=0 → mid=0, nums[0]=3, last=3

3 == 3 → AMBIGUOUS again. Shrink right: right=-1.

4
left=0 > right=-1 → loop ends

Return nums[boundary] = nums[2] = 1. Correct!

!

Worst case degrades to O(n): If the entire array is the same value (e.g. [2,2,2,2,2]), the tie-breaking fires every iteration and we shrink by one each time. This is unavoidable — you can't distinguish a rotated from non-rotated array with all-same elements faster than O(n). The problem statement says "minimise operations", acknowledging this worst case.

Solution

LC 153 + one extra branch

class Solution {
    public int findMin(int[] nums) {
        int left = 0;
        int right = nums.length - 1;
        int boundary = 0;

        while (left <= right) {
            int mid = left + (right - left) / 2;
            int last = nums[nums.length - 1];

            if (nums[mid] < last) {
                // Clearly in lower segment — could be minimum
                boundary = mid;
                right = mid - 1;
            } else if (nums[mid] > last) {
                // Clearly in upper segment — minimum is to the right
                left = mid + 1;
            } else {
                // nums[mid] == last: ambiguous — could be either side.
                // Safely shrink right boundary. We don't lose the min
                // because nums[right] == nums[mid] duplicates it.
                boundary = mid; // mid is a valid candidate
                right--;
            }
        }

        return nums[boundary];
    }
}
class Solution:
    def findMin(self, nums: list[int]) -> int:
        left, right = 0, len(nums) - 1
        boundary = 0

        while left <= right:
            mid = left + (right - left) // 2
            last = nums[-1]

            if nums[mid] < last:
                # Clearly in lower segment — could be minimum
                boundary = mid
                right = mid - 1
            elif nums[mid] > last:
                # Clearly in upper segment — minimum is to the right
                left = mid + 1
            else:
                # nums[mid] == last: ambiguous.
                # Shrink right — safe because nums[right] duplicates nums[mid].
                boundary = mid  # mid is a valid candidate
                right -= 1

        return nums[boundary]

Complexity

Time
O(log n) avg
O(n) worst case when all elements are identical — unavoidable.
Space
O(1)
Constant extra space regardless of input.
↑ Pattern map