Find Min Rotated Sorted Array II LeetCode 154

LeetCode 154 — Find Minimum in Rotated Sorted Array II — gives you a sorted array that has been rotated between 1 and n times, and may contain duplicates. Return the minimum element. This is the harder version of LeetCode 153 which guarantees no duplicates.

Without duplicates, binary search cleanly divides the search space in half each step. With duplicates, there is an ambiguous case: when nums[mid] == nums[right], we cannot determine which half contains the minimum. This single edge case changes the worst-case complexity from O(log n) to O(n).

The solution modifies the standard rotated array binary search by adding a third branch: when nums[mid] == nums[right], simply decrement right by 1. This safely shrinks the search space without risking skipping the minimum.

Initialize left = 0 and right = n - 1. While left < right, compute mid = left + (right - left) / 2. Compare nums[mid] with nums[right] to decide which half to search.

Case 1: nums[mid] < nums[right]. The minimum is in the left half (including mid). Set right = mid. Case 2: nums[mid] > nums[right]. The minimum is in the right half (excluding mid). Set left = mid + 1. These two cases are identical to the no-duplicates version.

Case 3: nums[mid] == nums[right]. We cannot determine which half contains the minimum. However, since nums[right] equals nums[mid], we can safely remove nums[right] from consideration by setting right = right - 1. This does not skip the minimum because mid holds the same value.

When nums[mid] == nums[right], decrementing right removes one element from the search space. This is safe because: if nums[right] is the minimum, nums[mid] has the same value and is still in the search space. We never lose the minimum.

This is the only correct move in the ambiguous case. We cannot set right = mid (might skip elements between mid+1 and right-1 that could be the minimum). We cannot set left = mid + 1 (might skip the minimum at mid). Decrementing right by 1 is the conservative choice.

The cost is that this step only reduces the search space by 1, not by half. In the worst case (all elements equal), we decrement right n times, giving O(n). But for typical inputs with few duplicates, the algorithm still runs in O(log n) on average.

Consider nums = [2, 2, 2, 0, 1]. left=0, right=4. mid=2, nums[2]=2, nums[4]=1. 2 > 1, minimum in right half: left=3. mid=3, nums[3]=0, nums[4]=1. 0 < 1, minimum in left half: right=3. left==right==3, return nums[3]=0.

Now consider nums = [1, 1, 1, 1, 1]. left=0, right=4. mid=2, nums[2]=1==nums[4]=1, right=3. mid=1, nums[1]=1==nums[3]=1, right=2. mid=1, nums[1]=1==nums[2]=1, right=1. left==right==1, return nums[1]=1. This took 3 steps (O(n)).

Mixed case: nums = [3, 3, 1, 3]. left=0, right=3. mid=1, nums[1]=3==nums[3]=3, right=2. mid=1, nums[1]=3 > nums[2]=1, left=2. left==right==2, return nums[2]=1. Only 2 steps despite duplicates.

In Python: left, right = 0, len(nums) - 1. While left < right: mid = (left + right) // 2. If nums[mid] < nums[right]: right = mid. Elif nums[mid] > nums[right]: left = mid + 1. Else: right -= 1. Return nums[left].

In Java: int left = 0, right = nums.length - 1. Same while loop and three-way comparison. Return nums[left]. The logic is identical — just syntax differences.

Note the subtle difference from LeetCode 153 (no duplicates): the only addition is the else branch with right -= 1. If you have solved 153, adding this one line handles all duplicate cases. This makes it an excellent follow-up question in interviews.

Average time complexity is O(log n) when duplicates are sparse. Each step either halves the search space (cases 1 and 2) or reduces it by one (case 3). With k duplicate groups, the expected time is O(log n + k).

Worst-case time complexity is O(n) when all elements are identical or nearly so. Example: [1, 1, 1, ..., 1]. Every step hits case 3 and decrements right by 1, taking n-1 steps.

Space complexity is O(1) — only three integer variables. This is the same as the no-duplicates version. The duplicate handling adds no extra memory, just potentially more iterations.

Find Minimum in Rotated Sorted Array (LeetCode 153) is the prerequisite without duplicates. Solving 153 first gives you the clean two-case binary search; 154 adds the third case for duplicates. Always present 153 before 154 in interviews.

Search in Rotated Sorted Array II (LeetCode 81) applies the same duplicate-handling technique to searching for a target value instead of the minimum. The right -= 1 trick is identical. Mastering 154 directly transfers to 81.

Find Peak Element (LeetCode 162) and Search a 2D Matrix II (LeetCode 240) are other binary search problems with non-standard search space reduction. Together with the rotated array family, they form a comprehensive binary search practice set.