Problem Statement in English

You’re given a rotated sorted array nums which may contain duplicates. You need to find the minimum element in this array. The array was originally sorted in ascending order and then possibly rotated at some pivot unknown to you beforehand.

Return the minimum element in the array.

Approach

Even though the array is rotated, it is still partially sorted. We can use a modified binary search to find the minimum element efficiently. The key is to compare the middle element with the rightmost element to determine which half of the array contains the minimum.

The cases we need to consider are:

  1. If the middle element is greater than the rightmost element, then the minimum must be in the right half of the array - so we move the left pointer to m + 1.
  2. If the middle element is less than the rightmost element, then the minimum must be in the left half of the array (including the middle element) - so we move the right pointer to m.
  3. If the middle element is equal to the rightmost element, we can’t determine which half contains the minimum - so we move the right pointer right -= 1 to safely shrink the search space.

And we’re done!

Solution in Python


class Solution:
    def findMin(self, nums: List[int]) -> int:
        left, right = 0, len(nums) - 1
        
        while left < right:
            m = (left + right) // 2
            
            if nums[m] > nums[right]:
                # Minimum must be in the right half
                left = m + 1
            elif nums[m] < nums[right]:
                # Minimum must be at m or to the left
                right = m
            else:
                # nums[m] == nums[right]
                # We can't decide which half, so we just shrink the window safely
                right -= 1
                
        return nums[left]

Complexity

  • Time: $O(\log n)$
    Since we are using binary search.

  • Space: $O(1)$
    Since we are using constant space.

Mistakes I Made

I overcomplicated the different cases.

And we are done.