Minimum in rotated sorted array II

Problem Statement:

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.

Solution:

• Same as Minimum in rotated sorted array, only need one more condition to check duplicates.

class Solution {
    public int findMin(int[] nums) {
        int start = 0;
        int end = nums.length - 1;
        int ans = Integer.MAX_VALUE;
        
        // Use binary search to find the minimum element in a rotated sorted array.
        while(start <= end){
            int mid = start + (end - start) / 2;
            
            /* 
            Handle duplicates:
	            - By having identical elements at the boundaries, we cannot determine if 
		            the minimum is on the left side or right side just based on these elements.
	            - If `nums[start] == nums[end]`, it suggests that there might be duplicates 
	            present which can confuse the binary search partition logic. 
            */
            if(nums[start] == nums[end]){
                ans = Math.min(ans, nums[start]);
                start++;
                end--;
            }
            // If the left part (from start to mid) is sorted
            else if(nums[start] <= nums[mid]){
                // Update the answer with the minimum value found so far
                ans = Math.min(ans, nums[start]);
                // Discard the left part and focus on the right part
                start = mid + 1;
            } else { // If the right part (from mid to end) is sorted
                // Update the answer with the minimum value found so far
                ans = Math.min(ans, nums[mid]);
                // Discard the right part and focus on the left part
                end = mid - 1;
            }
        }
 
        return ans;
    }
}