Find Minimum in Rotated Sorted Array II — Duplicates Handling

Problem 336 · Find Minimum in Rotated Sorted Array II

Difficulty: Hard · Pattern: Rotated + Duplicates

Same as find minimum but array may have duplicates.

Intuition

When nums[mid] == nums[hi], we can't determine which side is sorted, so hi-- (safe shrink).

Solutions

# Python
def findMin(nums):
    lo, hi = 0, len(nums)-1
    while lo < hi:
        mid = (lo+hi)//2
        if nums[mid] > nums[hi]: lo = mid+1    # min in right
        elif nums[mid] < nums[hi]: hi = mid     # min in left or mid
        else: hi -= 1                            # can't tell, safely shrink
    return nums[lo]

// Java
public int findMin(int[] nums) {
    int lo=0, hi=nums.length-1;
    while (lo<hi) {
        int mid=lo+(hi-lo)/2;
        if (nums[mid]>nums[hi]) lo=mid+1;
        else if (nums[mid]<nums[hi]) hi=mid;
        else hi--;
    }
    return nums[lo];
}

Complexity

Time: O(log n) average, O(n) worst case
Space: O(1)