LeetCode 154 - Find Minimum in Rotated Sorted Array II
This problem asks us to find the minimum value in a sorted array that has been rotated, while also allowing duplicate values. A rotated sorted array is created by taking an ascending sorted array and shifting some suffix of the array to the front.
Difficulty: 🔴 Hard
Topics: Array, Binary Search
Solution
Problem Understanding
This problem asks us to find the minimum value in a sorted array that has been rotated, while also allowing duplicate values.
A rotated sorted array is created by taking an ascending sorted array and shifting some suffix of the array to the front. For example, the sorted array [0,1,4,4,5,6,7] rotated four times becomes [4,5,6,7,0,1,4]. Even though the order looks disrupted, the array still preserves an important property: it consists of two sorted portions, and the smallest element marks the rotation point.
The challenge becomes more difficult because the array can contain duplicates. In the simpler version of this problem, without duplicates, binary search works cleanly because comparisons always reveal which side contains the minimum. With duplicates, some comparisons become ambiguous because equal values can hide the rotation boundary.
The input is an integer array nums, which satisfies the following guarantees:
- The original array was sorted in ascending order.
- It was rotated between
1andntimes. - Duplicate values are allowed.
- The array always contains at least one element.
The expected output is a single integer, the minimum element in the array.
The constraints tell us several useful things:
1 <= n <= 5000, meaning the array size is moderate.nums[i]ranges between-5000and5000, so values may be negative.- Since the problem explicitly asks us to reduce the number of operations as much as possible, a naive linear scan is technically acceptable for the input size but does not satisfy the spirit of the problem. A binary-search-based approach is preferred.
There are several important edge cases that can trip up naive implementations. Arrays with all identical values such as [2,2,2,2] make it impossible to immediately determine which side contains the minimum. Arrays that are not effectively rotated, such as [1,2,3,4], should still return the first element. A single-element array like [7] must also be handled correctly. Another subtle case is when duplicates appear near the pivot, such as [2,2,2,0,1], where a careless binary search may discard the wrong half.
Approaches
Brute Force Approach
The simplest solution is to scan the array from left to right and keep track of the smallest value encountered.
Because every element is checked exactly once, this approach always finds the correct answer. Since the minimum element must exist somewhere in the array, examining all values guarantees correctness.
However, this method ignores the fact that the array is originally sorted and rotated. It does not exploit the structure of the input at all, making it inefficient compared to what binary search can potentially achieve.
Optimal Approach, Modified Binary Search
The key observation is that a rotated sorted array still retains enough ordering information to allow binary search.
In a normal rotated sorted array without duplicates, comparing nums[mid] and nums[right] reveals which side contains the minimum:
- If
nums[mid] < nums[right], the minimum lies in the left half, includingmid. - If
nums[mid] > nums[right], the minimum lies in the right half.
Duplicates complicate matters. Consider:
[2,2,2,0,2]
If nums[mid] == nums[right], we cannot determine which side contains the minimum because both halves could still be valid.
The insight is that when equality occurs, we can safely reduce the search space by decrementing right by one. Even if nums[right] is the minimum, another identical value still exists at mid, so we are not losing the answer.
This modified binary search preserves correctness while maintaining logarithmic behavior in many cases. However, in the worst case, heavy duplication may degrade performance to linear time.
| Approach | Time Complexity | Space Complexity | Notes |
|---|---|---|---|
| Brute Force | O(n) | O(1) | Scan every element and track the minimum |
| Optimal | O(log n) average, O(n) worst | O(1) | Modified binary search, duplicates may force linear shrinking |
Algorithm Walkthrough
Optimal Algorithm
- Initialize two pointers,
left = 0andright = len(nums) - 1.
These pointers represent the current search range where the minimum could exist.
2. Continue searching while left < right.
Once both pointers meet, we know the minimum element has been isolated. 3. Compute the middle index:
mid = left + (right - left) // 2
This avoids overflow concerns in languages like Go or Java, even though Python does not require it.
4. Compare nums[mid] with nums[right].
If nums[mid] < nums[right], then the right portion is sorted, and the minimum must lie in the left half, including mid.
Update:
right = mid
- If
nums[mid] > nums[right], then the rotation point must lie to the right ofmid, meaning the minimum cannot be atmid.
Update:
left = mid + 1
- If
nums[mid] == nums[right], we cannot determine which side contains the minimum because duplicates create ambiguity.
Safely reduce the search space:
right -= 1
This works because removing one duplicate does not eliminate the only occurrence of the minimum.
7. When the loop finishes, left == right, and that position contains the minimum value.
8. Return:
nums[left]
Why it works
The algorithm maintains the invariant that the minimum element always remains inside the search range [left, right].
When nums[mid] < nums[right], the right side is sorted and larger, so the minimum must be at mid or before it. When nums[mid] > nums[right], the pivot lies to the right, so the minimum must be there. When values are equal, shrinking the range by removing right does not lose the minimum because an identical candidate still exists elsewhere. Since the interval shrinks every iteration, the algorithm eventually converges to the minimum element.
Python Solution
from typing import List
class Solution:
def findMin(self, nums: List[int]) -> int:
left = 0
right = len(nums) - 1
while left < right:
mid = left + (right - left) // 2
if nums[mid] < nums[right]:
right = mid
elif nums[mid] > nums[right]:
left = mid + 1
else:
right -= 1
return nums[left]
The implementation begins by initializing two pointers, left and right, which represent the search interval. The algorithm repeatedly narrows this interval until only one candidate remains.
Inside the loop, mid is computed as the middle index. The comparison between nums[mid] and nums[right] determines how the search space should shrink.
When nums[mid] < nums[right], the right side is sorted and the minimum must lie on the left side, including mid, so right = mid.
When nums[mid] > nums[right], the rotation point must lie to the right, meaning the minimum cannot be at mid, so left = mid + 1.
When both values are equal, duplicates prevent us from determining which half contains the minimum. In that case, right -= 1 safely removes one duplicate candidate.
Eventually, left and right converge to the same index, which contains the minimum value.
Go Solution
func findMin(nums []int) int {
left := 0
right := len(nums) - 1
for left < right {
mid := left + (right-left)/2
if nums[mid] < nums[right] {
right = mid
} else if nums[mid] > nums[right] {
left = mid + 1
} else {
right--
}
}
return nums[left]
}
The Go implementation follows the exact same logic as the Python solution. Since Go slices always know their length, no special handling is required for arrays versus slices.
The midpoint calculation uses:
mid := left + (right-left)/2
which avoids integer overflow in languages with fixed-width integers. Although the problem guarantees at least one element, the implementation assumes valid input as provided by LeetCode constraints.
Worked Examples
Example 1
Input:
nums = [1,3,5]
| Step | left | right | mid | nums[mid] | nums[right] | Action |
|---|---|---|---|---|---|---|
| 1 | 0 | 2 | 1 | 3 | 5 | 3 < 5, set right = mid |
| 2 | 0 | 1 | 0 | 1 | 3 | 1 < 3, set right = mid |
| End | 0 | 0 | - | - | - | Return nums[0] = 1 |
Final answer:
1
Example 2
Input:
nums = [2,2,2,0,1]
| Step | left | right | mid | nums[mid] | nums[right] | Action |
|---|---|---|---|---|---|---|
| 1 | 0 | 4 | 2 | 2 | 1 | 2 > 1, set left = mid + 1 |
| 2 | 3 | 4 | 3 | 0 | 1 | 0 < 1, set right = mid |
| End | 3 | 3 | - | - | - | Return nums[3] = 0 |
Final answer:
0
Duplicate Ambiguity Example
Input:
nums = [2,2,2,0,2]
| Step | left | right | mid | nums[mid] | nums[right] | Action |
|---|---|---|---|---|---|---|
| 1 | 0 | 4 | 2 | 2 | 2 | Equal, decrement right |
| 2 | 0 | 3 | 1 | 2 | 0 | 2 > 0, set left = mid + 1 |
| 3 | 2 | 3 | 2 | 2 | 0 | 2 > 0, set left = mid + 1 |
| End | 3 | 3 | - | - | - | Return nums[3] = 0 |
This example demonstrates why duplicates make the problem harder. Equality prevents us from immediately identifying the correct side, so the search interval must shrink conservatively.
Complexity Analysis
| Measure | Complexity | Explanation |
|---|---|---|
| Time | O(log n) average, O(n) worst | Binary search usually halves the search space, but duplicates can force one-by-one shrinking |
| Space | O(1) | Only a few pointer variables are used |
The average-case performance remains close to logarithmic because most comparisons still eliminate half the search range. However, in the worst case, such as [1,1,1,1,1], every comparison becomes ambiguous and only reduces the range by one element, degrading performance to O(n).
This is exactly how duplicates affect runtime complexity compared to the original problem without duplicates. The duplicate-free version guarantees O(log n) time, but duplicates introduce ambiguity that sometimes prevents binary elimination.
Test Cases
sol = Solution()
assert sol.findMin([1, 3, 5]) == 1 # provided example without rotation ambiguity
assert sol.findMin([2, 2, 2, 0, 1]) == 0 # provided example with duplicates
assert sol.findMin([1]) == 1 # single element array
assert sol.findMin([1, 2, 3, 4, 5]) == 1 # already sorted
assert sol.findMin([5, 1, 2, 3, 4]) == 1 # rotated once
assert sol.findMin([2, 3, 4, 5, 1]) == 1 # rotation near end
assert sol.findMin([2, 2, 2, 2, 2]) == 2 # all identical elements
assert sol.findMin([10, 10, 1, 10, 10]) == 1 # duplicates around pivot
assert sol.findMin([3, 3, 1, 3]) == 1 # minimum hidden among duplicates
assert sol.findMin([1, 1, 1, 0, 1]) == 0 # duplicate-heavy rotation
assert sol.findMin([-4, -3, -2, -1]) == -4 # negative values
assert sol.findMin([-1, 0, 1, -4, -3]) == -4 # rotated negatives
| Test | Why |
|---|---|
[1,3,5] |
Verifies basic non-duplicate behavior |
[2,2,2,0,1] |
Verifies duplicate handling |
[1] |
Validates smallest input size |
[1,2,3,4,5] |
Tests already sorted array |
[5,1,2,3,4] |
Tests pivot near beginning |
[2,3,4,5,1] |
Tests pivot near end |
[2,2,2,2,2] |
Worst-case duplicate scenario |
[10,10,1,10,10] |
Minimum surrounded by duplicates |
[3,3,1,3] |
Ambiguous duplicate comparisons |
[1,1,1,0,1] |
Heavy duplicate interference |
[-4,-3,-2,-1] |
Confirms negative values work |
[-1,0,1,-4,-3] |
Rotated negative values |
Edge Cases
Single Element Array
A one-element array such as [7] is an important edge case because the binary search loop never executes. A careless implementation might accidentally assume at least two elements exist and cause index issues. This implementation handles it naturally because left == right immediately, and the single value is returned.
All Elements Are Identical
An input like [2,2,2,2,2] is particularly tricky because every comparison becomes ambiguous. Since nums[mid] == nums[right] every time, the algorithm cannot determine which half contains the minimum and must shrink the range one step at a time. The implementation handles this correctly using right -= 1, although runtime degrades to O(n).
Duplicates Around the Rotation Point
Arrays like [10,10,1,10,10] are dangerous because duplicates can conceal the pivot. A naive binary search might incorrectly discard the wrong half if it assumes equality reveals ordering information. This implementation safely handles ambiguity by reducing the search interval conservatively whenever equal values appear.
Already Sorted Array
An array such as [1,2,3,4,5] may technically have been rotated n times, resulting in no visible rotation. Some implementations mistakenly assume the pivot must exist somewhere in the middle. Here, the binary search naturally converges to index 0, correctly returning the first element as the minimum.