Code Implementation

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

class Solution {
public:
    int findMin(vector<int>& nums) {
        int left = 0, right = nums.size() - 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];
    }
};
      

class Solution {
    public int findMin(int[] nums) {
        int left = 0, 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];
    }
}
      

var findMin = function(nums) {
    let left = 0, right = nums.length - 1;
    while (left < right) {
        let mid = left + Math.floor((right - left) / 2);
        if (nums[mid] < nums[right]) {
            right = mid;
        } else if (nums[mid] > nums[right]) {
            left = mid + 1;
        } else {
            right--;
        }
    }
    return nums[left];
};
      

Problem Description

You are given an array nums that was originally sorted in ascending order, but then rotated at some unknown pivot. Some elements in the array may be duplicates. Your task is to find and return the minimum element in nums.

• The array may contain duplicate values.
• There is at least one element in nums.
• It is guaranteed that the array was originally sorted, then rotated.
• Your solution should have better than linear time complexity if possible.

Thought Process

At first, you might think to simply scan through the array and keep track of the minimum element found so far. This brute-force approach is simple, but for large arrays, it is inefficient because it checks every element.

Since the array is a rotated version of a sorted array, we can often use binary search to find the minimum more quickly. However, the presence of duplicates complicates things, because when two elements are equal, we can't always tell which half of the array the minimum is in. This means we need to adjust the standard binary search to handle duplicates.

The key insight is to compare the middle element to the rightmost element to decide which half to search next, but if they're equal, we can't be sure, so we cautiously shrink the search space.

Solution Approach

• Initialize Pointers: Start with two pointers, left at the beginning and right at the end of the array.
• Binary Search Loop: While left < right:
  • Compute mid as the average of left and right.
  • Compare nums[mid] and nums[right]:
    • If nums[mid] < nums[right], the minimum is at mid or to its left. Set right = mid.
    • If nums[mid] > nums[right], the minimum is to the right of mid. Set left = mid + 1.
    • If nums[mid] == nums[right], we can't tell which half the minimum is in, but we can safely decrement right by 1, shrinking the search space by one.
• Result: When the loop ends, left points to the minimum element.

This approach handles duplicates by gradually narrowing the search space, and leverages the properties of the rotated sorted array to often skip large portions of the input.

Example Walkthrough

Let's walk through an example with nums = [2,2,2,0,1,2]:

1. Start: left = 0, right = 5 (nums[right] = 2)
2. First Iteration:
   • mid = 2 (nums[mid] = 2)
   • nums[mid] == nums[right], so decrement right to 4.
3. Second Iteration:
   • mid = 2 (nums[mid] = 2), right = 4 (nums[right] = 1)
   • nums[mid] > nums[right], so set left = mid + 1 = 3.
4. Third Iteration:
   • left = 3, right = 4
   • mid = 3 (nums[mid] = 0), nums[mid] < nums[right]
   • Set right = mid = 3
5. Now left == right == 3. The loop ends, and the minimum is nums[3] = 0.

At each step, the algorithm uses comparisons to discard as much of the array as possible, except when duplicates force a more cautious approach.

Time and Space Complexity

• Brute-force Approach: Scans every element, so time complexity is O(n). Space complexity is O(1) since no extra space is used.
• Optimized Approach (Binary Search with Duplicates):
  • In the best and average cases (few duplicates), time complexity is O(log n), as each comparison halves the search space.
  • In the worst case (all elements are duplicates), the time complexity degrades to O(n), since we might have to check each element.
  • Space complexity remains O(1) in all cases.

Summary

To find the minimum in a rotated sorted array that may contain duplicates, we use a modified binary search. By comparing the middle element to the rightmost element, we can often halve the search space. When duplicates prevent us from knowing which half to discard, we shrink the search space by one. This approach is efficient for most cases and gracefully handles the worst-case scenario, making it both practical and elegant.