Find Minimum in Rotated Sorted Array II: Handling Duplicates

Find Minimum in Rotated Sorted Array II is LeetCode 154, and it is the follow-up to LeetCode 153 that adds duplicates. The core algorithm is identical: binary search by comparing nums[mid] to nums[hi]. But when nums[mid] == nums[hi], you cannot determine which half contains the minimum, so you fall back to shrinking hi by one. That single edge case is the entire difference between this problem and the original.

The problem

You are given a sorted array of integers (possibly with duplicates) that has been rotated between 1 and n times. Find the minimum element.

Example: nums = [1, 3, 5] returns 1. nums = [2, 2, 2, 0, 1] returns 0.

The original sorted array [0, 1, 2, 2, 2] was rotated to produce [2, 2, 2, 0, 1]. The minimum still sits at the pivot point where the order breaks. The challenge is that duplicates at the boundaries can mask where that break is.

What changes with duplicates

In LeetCode 153 (no duplicates), comparing nums[mid] to nums[hi] always tells you which half the minimum is in:

• nums[mid] greater than nums[hi]: minimum is in [mid + 1, hi]
• nums[mid] less than nums[hi]: minimum is in [lo, mid]

With duplicates, a third case appears: nums[mid] == nums[hi]. Consider [1, 1, 0, 1]. At lo=0, hi=3, mid=1, you have nums[1] = 1 and nums[3] = 1. Is the minimum in the left half [1, 1] or the right half [0, 1]? You cannot tell. The values at mid and hi are equal, so neither half can be ruled out based on the comparison alone.

Visual walkthrough

First, a case where duplicates do not cause trouble: find the minimum in [2, 2, 2, 0, 1]. Then the ambiguous case that demonstrates why duplicates need special handling.

The first example resolves cleanly because nums[mid] and nums[hi] happen to differ. The second example is the important one. With [1, 1, 0, 1], the initial comparison gives nums[mid] == nums[hi], so you shrink hi by one. After that shrink, the ambiguity disappears and normal binary search logic takes over.

The code

Here is the complete Python solution for LeetCode 154, Find Minimum in Rotated Sorted Array II:

def find_min(nums):
    lo, hi = 0, len(nums) - 1

    while lo < hi:
        mid = lo + (hi - lo) // 2

        if nums[mid] > nums[hi]:
            lo = mid + 1
        elif nums[mid] < nums[hi]:
            hi = mid
        else:
            hi -= 1

    return nums[lo]

The structure is nearly identical to LeetCode 153. The only addition is the else: hi -= 1 branch.

if nums[mid] > nums[hi]: the rotation break is to the right. The minimum cannot be at mid (something smaller exists to its right), so set lo = mid + 1.

elif nums[mid] < nums[hi]: the right half is sorted and contains no break. The minimum is at mid or to the left. Set hi = mid (not mid - 1, because mid itself might be the answer).

else: hi -= 1: this is the new branch. nums[mid] == nums[hi], so you cannot determine which half has the minimum. Shrink hi by one. This is safe because nums[hi] has the same value as nums[mid], which is still in range. Even if nums[hi] was the minimum, its duplicate at mid preserves the answer.

Why shrinking hi is safe

When nums[mid] == nums[hi], you know three things:

1. nums[hi] and nums[mid] hold the same value.
2. mid is strictly less than hi (because lo is less than hi and mid = lo + (hi - lo) // 2).
3. If nums[hi] happened to be the minimum, then nums[mid] is also the minimum and mid is still in range after hi shrinks.

So decrementing hi by one never loses the answer. You just cannot cut the search space in half this time.

Complexity analysis

Time: O(n) worst case, O(log n) average. In the worst case, every element is identical except the minimum (for example, [1, 1, 1, 1, 0, 1, 1]). Each ambiguous step only shrinks the range by 1, so you scan nearly the entire array. When duplicates are sparse, the algorithm behaves like standard binary search and runs in O(log n).

Space: O(1). Three variables: lo, hi, mid. No extra data structures.

The O(n) worst case is unavoidable. When most elements are the same, no comparison-based algorithm can do better than linear.

Edge cases to watch for

• No rotation: nums = [1, 2, 3, 4, 5]. nums[mid] is never greater than nums[hi], so hi keeps moving left until lo == hi == 0. Returns 1.
• All same elements: nums = [3, 3, 3, 3]. Every step hits the else branch and shrinks hi by 1. Eventually lo == hi and returns 3. This is the O(n) worst case.
• Minimum at the start: nums = [0, 1, 2, 2, 2]. No rotation happened. The minimum is at index 0 and the algorithm converges left correctly.
• Minimum at the end: nums = [2, 3, 4, 5, 1]. Standard binary search finds the pivot at the last element.
• Minimum in the middle: nums = [3, 4, 0, 1, 2]. The pivot is at index 2. The algorithm narrows to it through the nums[mid] > nums[hi] branch.
• Two elements: nums = [2, 1]. mid = 0, nums[0] = 2 is greater than nums[1] = 1, so lo = 1. lo == hi, return 1.

The building blocks

This problem uses two building blocks:

Modified binary search. The same skeleton from LeetCode 153: maintain [lo, hi], compute mid, compare nums[mid] to nums[hi], and eliminate half the range. If you can write the LeetCode 153 solution from memory, this problem is one extra else branch on top.

Ambiguity resolution by linear shrink. When duplicates make the binary comparison useless, you fall back to removing one element at a time. This is the same pattern you see in Search in Rotated Sorted Array II (LeetCode 81): when you cannot make a binary decision, reduce the problem size by a constant and try again.

# LeetCode 153 (no duplicates):
while lo < hi:
    mid = lo + (hi - lo) // 2
    if nums[mid] > nums[hi]:
        lo = mid + 1
    else:
        hi = mid

# LeetCode 154 (with duplicates):
while lo < hi:
    mid = lo + (hi - lo) // 2
    if nums[mid] > nums[hi]:
        lo = mid + 1
    elif nums[mid] < nums[hi]:
        hi = mid
    else:
        hi -= 1

The else branch that was implicit in LeetCode 153 (folded into hi = mid) now splits into two: the clear case (nums[mid] less than nums[hi]) and the ambiguous case (nums[mid] == nums[hi]). Everything else is identical.

From understanding to recall

If you have already drilled LeetCode 153, the delta here is small: one extra else branch. But in an interview, small deltas are exactly what trip you up. Do you shrink hi or lo? By 1 or by setting it to mid? Do you use hi -= 1 or hi = mid - 1?

Those details matter, and they are easy to confuse under pressure. Spaced repetition locks them in. Type the full solution from scratch today, then again in two days, then in a week. By the third repetition, the else: hi -= 1 flows out automatically. You are not rederiving it under time pressure. You just know it.

LeetCode 154 is a great SRS candidate precisely because it is so close to LeetCode 153. The risk is not that you will forget the entire algorithm. The risk is that you will forget the one line that handles duplicates. Drilling makes that one line permanent.

Related posts

• Find Minimum in Rotated Sorted Array (LeetCode 153) - The no-duplicates version. Master this first, then LeetCode 154 is one extra branch on top
• Search in Rotated Sorted Array II (LeetCode 81) - Uses the same duplicate-ambiguity resolution pattern, but searches for a target instead of the minimum