# LeetCode 154: Find Minimum in Rotated Sorted Array II

## Problem Restatement

We are given an integer array `nums`.

The array was originally sorted in ascending order, then rotated. Unlike LeetCode 153, this version may contain duplicate values.

We need to return the minimum element.

The problem asks us to reduce the number of operations as much as possible. The constraints allow `1 <= nums.length <= 5000`, values between `-5000` and `5000`, and the array is sorted and rotated between `1` and `n` times.

## Input and Output

| Item | Meaning |
|---|---|
| Input | A rotated sorted integer array `nums` |
| Output | The minimum element |
| Duplicate values | Allowed |
| Required goal | Use as few operations as possible |

Example function shape:

```python
def findMin(nums: list[int]) -> int:
    ...
```

## Examples

Example 1:

```python
nums = [1, 3, 5]
```

The array is already sorted after rotation.

The minimum is:

```python
1
```

Example 2:

```python
nums = [2, 2, 2, 0, 1]
```

The minimum appears after the rotation point.

The answer is:

```python
0
```

Example 3:

```python
nums = [1, 1, 1, 1]
```

Every value is the same.

The minimum is:

```python
1
```

## First Thought: Linear Scan

The simplest method is to scan all numbers and keep the smallest value.

```python
class Solution:
    def findMin(self, nums: list[int]) -> int:
        best = nums[0]

        for num in nums:
            best = min(best, num)

        return best
```

This always works.

But it uses `O(n)` time.

Since the array is rotated sorted, we can usually do better with binary search.

## Key Insight

For LeetCode 153, all values are unique.

There, comparing `nums[mid]` and `nums[right]` tells us which side contains the minimum.

With duplicates, one extra case appears:

```python
nums[mid] == nums[right]
```

When this happens, we cannot know which side contains the minimum.

For example:

```python
nums = [1, 0, 1, 1, 1]
```

and:

```python
nums = [1, 1, 1, 0, 1]
```

Both can produce cases where `nums[mid] == nums[right]`.

The minimum may be on the left or the right.

But we can safely remove `right`.

Why?

Because `nums[mid] == nums[right]`, the value at `right` has a duplicate at `mid`.

If `nums[right]` is the minimum, then `nums[mid]` has the same minimum value, so removing `right` does not remove the only copy of the minimum.

So the duplicate case becomes:

```python
right -= 1
```

## Algorithm

Use binary search with two pointers:

```python
left = 0
right = len(nums) - 1
```

While `left < right`:

1. Compute `mid`.
2. If `nums[mid] > nums[right]`, the minimum is to the right of `mid`.
3. If `nums[mid] < nums[right]`, the minimum is at `mid` or to the left of `mid`.
4. If `nums[mid] == nums[right]`, shrink the search range by doing `right -= 1`.

When the loop ends, `left == right`.

Return:

```python
nums[left]
```

## Walkthrough

Use:

```python
nums = [2, 2, 2, 0, 1]
```

Start:

```python
left = 0
right = 4
```

Middle:

```python
mid = 2
nums[mid] = 2
nums[right] = 1
```

Since `2 > 1`, the minimum must be to the right.

Move:

```python
left = mid + 1 = 3
```

Now:

```python
left = 3
right = 4
```

Middle:

```python
mid = 3
nums[mid] = 0
nums[right] = 1
```

Since `0 < 1`, the minimum is at `mid` or to the left.

Move:

```python
right = mid = 3
```

Now:

```python
left = 3
right = 3
```

Return:

```python
nums[left] = 0
```

## Duplicate Walkthrough

Use:

```python
nums = [1, 1, 1, 0, 1]
```

Start:

```python
left = 0
right = 4
mid = 2
```

Compare:

```python
nums[mid] = 1
nums[right] = 1
```

They are equal, so we cannot decide which half contains the minimum.

But removing `right` is safe.

Move:

```python
right -= 1
```

Now:

```python
left = 0
right = 3
```

Middle:

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

Since `1 > 0`, the minimum must be to the right.

Move:

```python
left = mid + 1 = 2
```

Now:

```python
left = 2
right = 3
mid = 2
```

Compare:

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

Since `1 > 0`, move:

```python
left = mid + 1 = 3
```

Now `left == right`, so the answer is:

```python
nums[3] = 0
```

## Correctness

At every step, the minimum remains inside the range `[left, right]`.

If `nums[mid] > nums[right]`, then `mid` is in the larger left part of the rotated array. Since the rightmost value is smaller, the rotation point and the minimum must be to the right of `mid`. Moving `left` to `mid + 1` keeps the minimum.

If `nums[mid] < nums[right]`, then the range from `mid` to `right` is sorted in ascending order. The smallest value in that range is `nums[mid]`, so the minimum may be at `mid`, or it may be further left. Moving `right` to `mid` keeps both possibilities.

If `nums[mid] == nums[right]`, the rightmost value has another copy at `mid`. Removing `right` cannot remove the only copy of the minimum. If `nums[right]` is the minimum, then `nums[mid]` has the same value and remains in the search range. So `right -= 1` is safe.

When the loop ends, only one index remains. Since the minimum was never removed, that index contains the minimum element.

## Complexity

| Metric | Value | Why |
|---|---|---|
| Time | `O(log n)` average | Usually binary search halves the range |
| Time | `O(n)` worst case | Many duplicates may force `right -= 1` repeatedly |
| Space | `O(1)` | Only pointers are stored |

The worst case happens for arrays with many equal values, such as:

```python
[1, 1, 1, 1, 1]
```

or:

```python
[1, 1, 1, 0, 1, 1, 1]
```

In these cases, the algorithm may shrink the range one element at a time.

## Implementation

```python
class Solution:
    def findMin(self, nums: list[int]) -> int:
        left = 0
        right = len(nums) - 1

        while left < right:
            mid = (left + right) // 2

            if nums[mid] > nums[right]:
                left = mid + 1
            elif nums[mid] < nums[right]:
                right = mid
            else:
                right -= 1

        return nums[left]
```

## Code Explanation

We search inside the full array:

```python
left = 0
right = len(nums) - 1
```

The loop runs while more than one candidate remains:

```python
while left < right:
```

We compute the middle:

```python
mid = (left + right) // 2
```

If the middle value is larger than the rightmost value:

```python
if nums[mid] > nums[right]:
    left = mid + 1
```

then the minimum must be on the right side.

If the middle value is smaller than the rightmost value:

```python
elif nums[mid] < nums[right]:
    right = mid
```

then the minimum may be at `mid`, so we keep it.

If they are equal:

```python
else:
    right -= 1
```

we remove one duplicate from the right side.

Finally:

```python
return nums[left]
```

returns the only remaining candidate.

## Testing

```python
def run_tests():
    sol = Solution()

    assert sol.findMin([1, 3, 5]) == 1
    assert sol.findMin([2, 2, 2, 0, 1]) == 0
    assert sol.findMin([1, 1, 1, 1]) == 1
    assert sol.findMin([1]) == 1
    assert sol.findMin([2, 1]) == 1
    assert sol.findMin([1, 0, 1, 1, 1]) == 0
    assert sol.findMin([1, 1, 1, 0, 1]) == 0
    assert sol.findMin([3, 3, 1, 3]) == 1
    assert sol.findMin([10, 1, 10, 10, 10]) == 1

    print("all tests passed")

run_tests()
```

| Test | Why |
|---|---|
| `[1, 3, 5]` | Basic sorted case |
| `[2, 2, 2, 0, 1]` | Official duplicate-style case |
| `[1, 1, 1, 1]` | All values equal |
| `[1]` | Single element |
| `[2, 1]` | Two elements |
| `[1, 0, 1, 1, 1]` | Ambiguous duplicate case |
| `[1, 1, 1, 0, 1]` | Duplicate ambiguity on both sides |
| `[3, 3, 1, 3]` | Minimum hidden among duplicates |
| `[10, 1, 10, 10, 10]` | Worst-case style duplicate layout |