This is a follow-up to LeetCode 153, but with one important difference:

The rotated sorted array may contain duplicates.

Example:

Input: [2,2,2,0,1]
Output: 0

Because duplicates exist, the classic binary-search logic from problem 153 does not work directly and needs modification.

---

Understanding the Problem

The array is:

Sorted
Rotated at some pivot
Contains duplicates

Goal: return the minimum element.

Example:

Original sorted array: [0, 1, 2, 2, 2]
Possible rotation: [2, 2, 2, 0, 1]

Minimum is still 0.

The challenge is that duplicates can hide the pivot, breaking simple comparisons.

---

Why Duplicates Make It Hard

In problem 153 (no duplicates), comparing:

nums[mid] vs nums[right]

tells exactly which side is sorted and where the pivot lies.

But with duplicates:

nums[mid] = nums[right]

does not give any information.
Both halves could still be valid.

So we need a special rule to handle duplicates.

---

Approach (Explained in Simple Language)

We still use binary search, but with one extra rule.

1. Use two pointers

left = 0
right = n−1

2. Compute mid each step

mid = left + (right − left) / 2

3. Comparison logic

Case 1: nums[mid] < nums[right]
Minimum is in the left half including mid.
right = mid

Case 2: nums[mid] > nums[right]
Minimum is in the right half.
left = mid + 1

Case 3: nums[mid] == nums[right]
Duplicates → we cannot decide the direction.
So simply reduce search space:
right–

This is the only difference from problem 153.

4. When left == right

Minimum is nums[left].

This algorithm ensures worst-case O(n) (when many duplicates exist), but average is still O(log n).

---

Java Code

public class FindMinimumInRotatedSortedArrayII {

    public int findMin(int[] nums) {

        int left = 0;
        int right = nums.length - 1;

        while (left < right) {

            int mid = left + (right - left) / 2;

            if (nums[mid] < nums[right]) {

                right = mid;

            } else if (nums[mid] > nums[right]) {

                left = mid + 1;

            } else {

                right--;
            }
        }

        return nums[left];
    }

    public static void main(String[] args) {
        FindMinimumInRotatedSortedArrayII solution = new FindMinimumInRotatedSortedArrayII();
        int[] nums = {2,2,2,0,1};
        System.out.println(solution.findMin(nums));
    }
}

---

Dry Run

Input:
nums = [2, 2, 2, 0, 1]

left = 0
right = 4

---

Step 1

left = 0, right = 4
mid = 2
nums[mid] = 2
nums[right] = 1

2 > 1 → minimum is in right half

left = mid + 1 = 3

---

Step 2

left = 3, right = 4
mid = (3+4)/2 = 3

nums[mid] = 0
nums[right] = 1

0 < 1 → minimum is in left half including mid

right = mid = 3

---

Step 3

left = 3, right = 3
Exit loop.

Return nums[left] = 0

Minimum = 0

---

Why This Approach Works

Duplicates hide the pivot, so comparing mid and right becomes ambiguous when equal.

The rule right– safely reduces the search space without losing the minimum.

This guarantees correctness because:

If nums[mid] == nums[right],
We know nums[right] cannot be the unique minimum (since there are duplicates),
But nums[right] might still be equal to the minimum, so shrinking the search space preserves correctness.

Average complexity: O(log n)
Worst-case (all elements equal): O(n)