LeetCode Hard – Find Minimum in Rotated Sorted Array II

Suppose an array of length n sorted in ascending order is rotated between 1 and n times. For example, the array nums = [0,1,4,4,5,6,7] might become:

• [4,5,6,7,0,1,4] if it was rotated 4 times.
• [0,1,4,4,5,6,7] if it was rotated 7 times.

Notice that rotating an array [a[0], a[1], a[2], ..., a[n-1]] 1 time results in the array [a[n-1], a[0], a[1], a[2], ..., a[n-2]].

Given the sorted rotated array nums that may contain duplicates, return the minimum element of this array.

You must decrease the overall operation steps as much as possible.

Example 1:Input: nums = [1,3,5] Output: 1

Example 2:Input: nums = [2,2,2,0,1] Output: 0

Constraints:

• n == nums.length
• 1 <= n <= 5000
• -5000 <= nums[i] <= 5000
• nums is sorted and rotated between 1 and n times.

Java Solution

To solve this problem, you can perform a modified binary search. The idea is to compare the middle element with the rightmost element to determine whether the minimum element lies in the left or right half of the array. If the middle element is greater than the rightmost element, you know that the minimum is in the right half; otherwise, it is in the left half. Repeat this process until you find the minimum element.

Here’s the Java solution:

public class MinInRotatedSortedArrayII {
    public int findMin(int[] nums) {
        int left = 0;
        int right = nums.length - 1;

        while (left < right) {
            int mid = left + (right - left) / 2;

            if (nums[mid] > nums[right]) {
                // Minimum is in the right half
                left = mid + 1;
            } else if (nums[mid] < nums[right]) {
                // Minimum is in the left half or at the mid position
                right = mid;
            } else {
                // Handle duplicates, move right pointer towards left
                right--;
            }
        }

        return nums[left];
    }

    public static void main(String[] args) {
        MinInRotatedSortedArrayII solution = new MinInRotatedSortedArrayII();

        // Example 1
        int[] nums1 = {1, 3, 5};
        System.out.println(solution.findMin(nums1));  // Output: 1

        // Example 2
        int[] nums2 = {2, 2, 2, 0, 1};
        System.out.println(solution.findMin(nums2));  // Output: 0
    }
}

This Java code defines a MinInRotatedSortedArrayII class with the findMin method, which finds the minimum element in the rotated sorted array with duplicates. The provided test cases demonstrate its usage.

Python Solution

Here’s the equivalent Python solution for finding the minimum element in a rotated sorted array with duplicates:

class MinInRotatedSortedArrayII:
    def findMin(self, nums):
        left, right = 0, len(nums) - 1

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

            if nums[mid] > nums[right]:
                # Minimum is in the right half
                left = mid + 1
            elif nums[mid] < nums[right]:
                # Minimum is in the left half or at the mid position
                right = mid
            else:
                # Handle duplicates, move right pointer towards left
                right -= 1

        return nums[left]

# Test cases
solution = MinInRotatedSortedArrayII()

# Example 1
nums1 = [1, 3, 5]
print(solution.findMin(nums1))  # Output: 1

# Example 2
nums2 = [2, 2, 2, 0, 1]
print(solution.findMin(nums2))  # Output: 0

This Python code defines a MinInRotatedSortedArrayII class with the findMin method, which finds the minimum element in the rotated sorted array with duplicates. The provided test cases demonstrate its usage.