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

Example function shape:

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

Examples

Example 1:

nums = [1, 3, 5]

The array is already sorted after rotation.

The minimum is:

1

Example 2:

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

The minimum appears after the rotation point.

The answer is:

0

Example 3:

nums = [1, 1, 1, 1]

Every value is the same.

The minimum is:

1

First Thought: Linear Scan

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

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:

nums[mid] == nums[right]

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

For example:

nums = [1, 0, 1, 1, 1]

and:

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:

right -= 1

Algorithm

Use binary search with two pointers:

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:

nums[left]

Walkthrough

Use:

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

Start:

left = 0
right = 4

Middle:

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

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

Move:

left = mid + 1 = 3

Now:

left = 3
right = 4

Middle:

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

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

Move:

right = mid = 3

Now:

left = 3
right = 3

Return:

nums[left] = 0

Duplicate Walkthrough

Use:

nums = [1, 1, 1, 0, 1]

Start:

left = 0
right = 4
mid = 2

Compare:

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

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

But removing right is safe.

Move:

right -= 1

Now:

left = 0
right = 3

Middle:

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

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

Move:

left = mid + 1 = 2

Now:

left = 2
right = 3
mid = 2

Compare:

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

Since 1 > 0, move:

left = mid + 1 = 3

Now left == right, so the answer is:

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

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

[1, 1, 1, 1, 1]

or:

[1, 1, 1, 0, 1, 1, 1]

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

Implementation

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:

left = 0
right = len(nums) - 1

The loop runs while more than one candidate remains:

while left < right:

We compute the middle:

mid = (left + right) // 2

If the middle value is larger than the rightmost value:

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:

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

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

If they are equal:

else:
    right -= 1

we remove one duplicate from the right side.

Finally:

return nums[left]

returns the only remaining candidate.

Testing

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()