LeetCode 154. Find Minimum in Rotated Sorted Array II

https://leetcode.com/problems/find-minimum-in-rotated-sorted-array-ii/description/

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.

package LeetCode.binarySearch;

public class LT154_SearchInRotatedSortedArray_duplicates {

    public static void main(String[] args) {
        int[] arr = {1};

        System.out.println(findMin(arr));
        // TC: O(log n) in best/average case, O(n) in worst case due to duplicates
        // SC: O(1)
    }

    public static int findMin(int[] nums) {
        int low = 0, high = nums.length - 1; // SC: O(1), initializing variables

        int min = Integer.MAX_VALUE; // SC: O(1), auxiliary variable to track min
        while (low <= high) {        // TC: O(log n) best/avg, O(n) worst when duplicates reduce one by one
            int mid = low + (high - low) / 2; // SC: O(1)

            if (nums[low] < nums[high]) {    // TC: O(1), check if already sorted
                return Integer.min(nums[low], min); // SC: O(1)
            }

            if (nums[low] == nums[mid] && nums[mid] == nums[high]) { // TC: O(1)
                min = Integer.min(nums[low], min); // SC: O(1)
                low++;  // TC: O(1)
                high--; // TC: O(1)
            }
            // left half is sorted
            else if (nums[low] <= nums[mid]) {  // TC: O(1)
                min = Integer.min(nums[low], min); // SC: O(1)
                low = mid + 1; // TC: O(1)
            } else {
                min = Integer.min(nums[mid], min); // SC: O(1)
                high = mid - 1; // TC: O(1)
            }
        }

        return min; // SC: O(1)
    }
}

Here’s the Time and Space Complexity of the findMin function in a clear table format:

Case	Time Complexity	Space Complexity
Best	O(1)	O(1)
Average	O(log n)	O(1)
Worst	O(n)	O(1)

Explanation:

• Best Case: The array is already sorted (nums[low] < nums[high]).

• Average Case: Standard binary search logic with occasional duplicates.

• Worst Case: All or many elements are duplicates, causing the loop to degrade into linear time.