Find Minimum in Rotated Sorted Array II

Find Minimum in Rotated Sorted Array II is the harder twin of the classic rotated-array search. The array was sorted, then rotated — and this time it may contain duplicates. Those duplicates are exactly what break the clean version, so the fix is the interesting part.

The slow way first

The obvious idea: scan the whole array and track the smallest value. That is O(n) and ignores all the structure. A rotated sorted array is almost sorted — there is exactly one place where a big value drops to a small one, and the minimum sits right there. Binary search should find it in roughly O(log n).

The question to ask: standing at the middle, which half must contain the minimum? We answer it by comparing nums[mid] to the right end nums[hi].

The idea: compare mid to the right end

Keep a window [lo, hi] and look at mid.

• If nums[mid] > nums[hi], the drop is to the right of mid, so the min is too — move lo = mid + 1.
• If nums[mid] < nums[hi], that half is already in order and mid itself could be the min — move hi = mid.
• If nums[mid] == nums[hi], we genuinely cannot tell which side holds the min. But hi is duplicated, so dropping it changes nothing — do hi -= 1.

That equal-case hi -= 1 is the whole point of the II version. It is why the worst case slips to O(n): an array of all equal values forces us to peel hi off one at a time.

Walk through it

Step through the animation. The three pointers lo, mid, and hi mark the window. When nums[mid] ties nums[hi] we shave hi; when it is bigger we jump lo past mid; when it is smaller we pull hi down to mid. The window collapses onto the 0.

Pseudocode

lo = 0
hi = last index
while lo < hi:
    mid = midpoint of lo and hi
    if nums[mid] > nums[hi]:
        lo = mid + 1            # min is strictly to the right
    else if nums[mid] < nums[hi]:
        hi = mid                # min is mid or to its left
    else:
        hi = hi - 1             # duplicate at hi, safe to drop
return nums[lo]                 # lo == hi: the minimum

The Python solution

def find_min(nums):
    lo = 0
    hi = len(nums) - 1
    while lo < hi:
        mid = (lo + hi) // 2
        if nums[mid] > nums[hi]:
            lo = mid + 1
        elif nums[mid] < nums[hi]:
            hi = mid
        else:
            hi -= 1
    return nums[lo]

• We compare against nums[hi], the right end — comparing against nums[lo] does not work cleanly when the array is not rotated.
• nums[mid] > nums[hi]: the wrap-around is right of mid, so lo = mid + 1 skips mid (it cannot be the min).
• nums[mid] < nums[hi]: we set hi = mid, not mid - 1, because mid itself might be the minimum.
• The else branch handles ties with hi -= 1: dropping a duplicated end value can never discard the only copy of the minimum.
• The loop runs while lo < hi; when they meet, nums[lo] is the answer.

Complexity

Duplicates cost us the guarantee: in the all-equal case the binary search degrades to a linear scan. With no duplicates the same code is always O(log n).

When this pattern shows up

Practice