Find Minimum in Rotated Sorted Array II — Duplicates and the Safe Shrink [LC 154, Google]

Problem Statement#

Given a sorted rotated array nums that may contain duplicates, return the minimum element of the array.

Constraints:

• n == nums.length
• 1 <= n <= 5000
• -5000 <= nums[i] <= 5000
• nums is sorted and rotated between 1 and n times
• Duplicates are allowed

Input:  nums = [1,3,5]
Output: 1

Input:  nums = [2,2,2,0,1]
Output: 0

Why This Problem Matters#

LC 154 is the hard follow-up to LC 153 (Find Minimum in Rotated Sorted Array) and is asked by Google and Microsoft to test whether candidates understand the limits of binary search. In LC 153, all values are distinct, so comparing nums[mid] with nums[hi] always tells you which side the minimum is on. Duplicates break this: when nums[mid] == nums[hi], the minimum could be on either side.

This problem is important not for its algorithm (the fix is one line: hi -= 1) but for the reasoning it requires. Understanding exactly why hi -= 1 is safe — it removes one duplicate without discarding the actual minimum — and why it degrades to O(n) in the worst case demonstrates deep binary search understanding.

The Core Insight#

Three cases at each mid:

1. nums[mid] > nums[hi]: the rotation point is to the right of mid. Minimum is in right half. lo = mid + 1.
2. nums[mid] < nums[hi]: the minimum is at mid or to its left. hi = mid.
3. nums[mid] == nums[hi]: ambiguous. The minimum could be in either half. Safely shrink by hi -= 1 — we know nums[hi] is not the unique minimum (because nums[mid] is identical, so even if nums[hi] were the minimum, nums[mid] is an equally good candidate that still lies within the window).

The hi -= 1 operation is safe because it never discards an element that is the only copy of the minimum value.

Visual Dry Run#

Input: nums = [2, 2, 2, 0, 1]

Ambiguous case: nums = [3, 1, 3, 3, 3]

Solution (Optimal)#

class Solution:
    def findMin(self, nums: list[int]) -> int:
        lo, hi = 0, len(nums) - 1
 
        while lo < hi:
            mid = lo + (hi - lo) // 2
 
            if nums[mid] > nums[hi]:
                # Rotation point is strictly to the right of mid
                lo = mid + 1
            elif nums[mid] < nums[hi]:
                # Minimum is at mid or to the left of mid
                hi = mid
            else:
                # nums[mid] == nums[hi]: ambiguous — safely discard one duplicate from the right
                hi -= 1
 
        return nums[lo]

var findMin = function(nums) {
    let lo = 0, hi = nums.length - 1;
 
    while (lo < hi) {
        const mid = lo + Math.floor((hi - lo) / 2);
 
        if (nums[mid] > nums[hi]) {
            lo = mid + 1;       // rotation point is to the right
        } else if (nums[mid] < nums[hi]) {
            hi = mid;           // minimum is at mid or to the left
        } else {
            hi--;               // nums[mid] == nums[hi]: can safely remove this duplicate
        }
    }
 
    return nums[lo];
};

Time: O(log n) average, O(n) worst case (all identical elements) Space: O(1) — only pointer variables

Common Mistakes#

• Using lo++ instead of hi-- in the ambiguous case — both work, but hi-- is conventional when comparing to hi.
• Using hi = mid in the ambiguous case — this does not make progress when mid == hi, causing infinite loops.
• Forgetting this problem has a different worst case than LC 153 — always communicate the O(n) worst case to interviewers.
• Applying the LC 153 algorithm (two cases) directly — it gives wrong results when duplicates create the ambiguous case.

Interview Tips#

• Immediately state: "This is LC 153 with duplicates; the only new case is nums[mid] == nums[hi], which requires hi--."
• Explain WHY hi-- is safe: nums[hi] has a duplicate at nums[mid] that is still inside the window, so discarding nums[hi] cannot lose the minimum.
• State the worst-case complexity proactively: O(n) when all elements are equal (e.g., [1,1,1,1,1]).
• Mention that LC 81 (Search in Rotated Sorted Array II) uses the symmetric lo++ escape for the same reason.

Follow-up Questions#

• LC 153 (no duplicates): Two-case solution, guaranteed O(log n).
• LC 81 (search with duplicates): Uses lo++ when nums[lo] == nums[mid] for the symmetric reason.
• Can you always do O(log n)? No — the input [1,1,1,...,1,0,1] requires the search to eventually scan every element in the worst case.
• What if you need the index of the minimum, not the value? Return lo instead of nums[lo] after the loop.
• How does this extend to finding the minimum in a k-rotated array? Same algorithm — rotation count does not change the logic.

Key Takeaways#

• LC 154 is the hard variant of LC 153; the only difference is a third case: nums[mid] == nums[hi], handled by hi -= 1.
• The hi-- is safe because when nums[mid] == nums[hi], the minimum cannot be uniquely at hi — nums[mid] is an identical value still inside the window.
• Worst-case complexity is O(n) for all-equal arrays — this is provably unavoidable and must be disclosed in interviews.
• Use while lo < hi with hi = mid for the case nums[mid] < nums[hi] — never use hi = mid - 1 here or the minimum at mid gets skipped.
• Google and Microsoft ask this problem to verify that candidates can articulate invariant breakdown and worst-case bounds, not just produce code.
• LC 81 uses the same escape-hatch reasoning on the lo side: lo++ when nums[lo] == nums[mid] makes the left-sorted check unambiguous.
• This problem is a litmus test for depth of understanding: the algorithm is nearly identical to LC 153, but the reasoning is fundamentally different.