Leetcode 154: Find Minimum in Rotated Sorted Array II

The original question can be found here.

This question is asking to find the mimimum element in a rotated sorted array. But before tackling this question, I strongly suggest you to look at this question if you haven’t already.

However, this question is not that easy since the numbers can be duplicate. Let’s say we meet this case:

Since nums[start] == nums[end], we don’t know which part middle index is at. But determine the location of middle index is critical in this problem, as described in Leetcode 153: Find Minimum in Rotated Sorted Array, we need to shrink either start or end boundaries.

class Solution:
    def findMin(self, nums: List[int]) -> int:
        left, right = 0, len(nums) - 1
        while left + 1 < right:
            while left + 1 < right and nums[left] == nums[right]:
                left += 1
            if left + 1 >= right:
                break
            mid = (left + right) // 2
            if nums[mid] <= nums[right]:
                right = mid
            else:
                left = mid

        return nums[left] if nums[left] <= nums[right] else nums[right]

Time Complexity: Best case O(logn), and worst case O(n) if all numbers are equal. Space Complexity: O(1).