Find Minimum in Rotated Sorted Array II
Find the smallest value in a rotated sorted array that may hold duplicates: binary search, shrinking the right end by one when the middle ties with it.
Updated Long read: 9 min read
Approaches at a glance
| Approach | Time | Space |
|---|---|---|
| Scan every item | O(n) | O(1) |
| Binary search, shrinking on ties | O(log n) typical, O(n) worst case | O(1) |
The problem
An array of integers was sorted in ascending order and then rotated: some number of items were moved from the front to the end, keeping their order. The amount is unknown and may be zero. This time values may repeat.
Return the smallest value in the array, doing as little work as you can.
numbers = [4, 4, 5, 1, 4, 4, 4] → 1
numbers = [3, 3, 1, 3, 3, 3, 3] → 1
numbers = [2, 2, 6, 6, 9] → 2 (not rotated)
numbers = [8, 8, 8] → 8It is the same question as Find Minimum in Rotated Sorted Array with one word removed: "distinct". That one word is the difference between a medium problem and a hard one.
Approach 1: scan every item
Look at everything and keep the smallest.
JavaScript
function findRotatedMinWithDuplicatesLinear(numbers) {
let smallest = numbers[0];
for (const value of numbers) {
if (value < smallest) smallest = value;
}
return smallest;
}Python
def find_rotated_min_with_duplicates_linear(numbers):
smallest = numbers[0]
for value in numbers:
if value < smallest:
smallest = value
return smallestTime O(n). Space O(1). Usually a plain scan is only the warm-up. Here it deserves more respect, because, as shown further down, no method can promise to beat O(n) on every input.
Why the distinct-values search breaks
With distinct values, the search compares the middle item with the item at the right end of the range:
- middle larger than the right end: the drop is to the right, so
lo = mid + 1; - middle smaller than the right end: the middle to the right end is in order, so
hi = mid.
Those two rules are still correct when values repeat. What is new is a third outcome, middle equal to the right end, and it says nothing about where the smallest value is:
index 0 1 2 3 4 5 6
array A: [3, 3, 1, 3, 3, 3, 3] smallest is LEFT of the middle
array B: [3, 3, 3, 3, 3, 1, 3] smallest is RIGHT of the middle
↑ ↑
mid hi both are 3 in both arraysBoth are properly rotated sorted arrays (each is a rotation of [1, 3, 3, 3, 3, 3, 3]). In both, the middle is 3 and the right end is 3. Code that treats a tie as "go left" gets A right and returns 3 for B. Code that treats it as "go right" fails on A. No fixed choice works.
Approach 2: binary search, shrinking on ties
When the middle equals the right end, there is one thing that is certain: the right end can be thrown away safely. If it happens to be the smallest value, the middle holds an equal value and is still in the range, so the answer survives. So on a tie, move hi down by one and ask again.
JavaScript
function findRotatedMinWithDuplicates(numbers) {
let lo = 0;
let hi = numbers.length - 1;
while (lo < hi) {
const mid = lo + Math.floor((hi - lo) / 2);
if (numbers[mid] > numbers[hi]) {
lo = mid + 1; // the drop is to the right of mid
} else if (numbers[mid] < numbers[hi]) {
hi = mid; // mid..hi is in order, so mid may be the smallest
} else {
hi--; // a tie: no way to tell, so discard one item
}
}
return numbers[lo];
}Python
def find_rotated_min_with_duplicates(numbers):
lo = 0
hi = len(numbers) - 1
while lo < hi:
mid = lo + (hi - lo) // 2
if numbers[mid] > numbers[hi]:
lo = mid + 1 # the drop is to the right of mid
elif numbers[mid] < numbers[hi]:
hi = mid # mid..hi is in order, so mid may be the smallest
else:
hi -= 1 # a tie: no way to tell, so discard one item
return numbers[lo]The loop keeps one promise from start to finish: a copy of the smallest value is somewhere from lo to hi. Check each branch against it.
- Middle larger. The middle is not the smallest (the right end is smaller), and nor is anything to its left within the range, since those items are in the same climbing run as the middle or the drop would already be behind it. Moving
lopast the middle keeps the promise. - Middle smaller. Everything right of the middle is at least as large as the middle. Dropping those items keeps the promise.
- Tie. Only the right end is removed, and an equal value remains at
mid, which is always less thanhiwhile the loop runs.
Removing hi can cut the range in an odd place, so what is left may no longer be a neat rotation with its drop intact. That does not matter. The promise is about a value, not about the shape of the range, and the first two rules only rely on the values still climbing, with at most one drop, from lo to hi. Taking an item off the end cannot add a drop.
Walkthrough
Array A, [3, 3, 1, 3, 3, 3, 3]:
| lo | hi | mid (value) | Right end | Result | Action |
|---|---|---|---|---|---|
| 0 | 6 | 3 (3) | 3 | Tie | hi = 5 |
| 0 | 5 | 2 (1) | 3 | Smaller | hi = 2 |
| 0 | 2 | 1 (3) | 1 | Larger | lo = 2 |
| 2 | 2 | lo and hi have met | Return numbers[2] = 1 |
Array B, [3, 3, 3, 3, 3, 1, 3]:
| lo | hi | mid (value) | Right end | Result | Action |
|---|---|---|---|---|---|
| 0 | 6 | 3 (3) | 3 | Tie | hi = 5 |
| 0 | 5 | 2 (3) | 1 | Larger | lo = 3 |
| 3 | 5 | 4 (3) | 1 | Larger | lo = 5 |
| 5 | 5 | lo and hi have met | Return numbers[5] = 1 |
The first row is identical for both arrays. The search could not tell them apart, gave up one item, and the second look settled it: with hi at 5, the right end is 3 in A and 1 in B, and the two searches part company.
Why the worst case is O(n)
Take an array of all 3s. Every comparison is a tie, so hi moves down one place at a time: n - 1 steps for n items. The same happens for most of the way on an array of 3s with a single 1 near the front.
This is not carelessness in the code. Think of someone who has built an array of n threes and is allowed to swap a single 1 into any position they like; wherever it goes, the result is a valid rotated sorted array. Your method inspects positions one at a time and sees a 3 each time. While any position remains unseen, the 1 could be hiding there, so answering "3" might be wrong, and answering "1" might be wrong too, because there may be no 1 at all. Only after looking at every position can the method be sure. So any correct method must look at all n items on some inputs, and O(n) in the worst case cannot be improved.
What binary search buys is the common case. Each tie costs one step, and each clear comparison still halves the range. With few repeated values the running time stays close to O(log n); it slides towards O(n) only as ties pile up.
Time: O(n) in the worst case, O(log n) when ties are rare. Space O(1).
Comparing the approaches
| Scan every item | Binary search, shrinking on ties | |
|---|---|---|
| Worst-case time | O(n) | O(n) |
| Time with few duplicates | O(n) | O(log n) |
| Space | O(1) | O(1) |
| Steps for 1,000,000 distinct values | 1,000,000 | About 20 |
| Steps for 1,000,000 equal values | 1,000,000 | 999,999 |
| Chance of a subtle bug | Very low | Real: three branches, each with its own bound update |
If the data is known to be mostly duplicates, the scan is the sensible choice. If duplicates are occasional, the binary search is far faster. The wider family of these problems is laid out in the rotated sorted arrays pattern.
Try it yourself
Copy a solution from above, add the lines below, and run it. For JavaScript, paste both into the browser console, or save them in a file and run it with node. For Python, save them in a file and run it with python.
JavaScript
console.log(findRotatedMinWithDuplicates([4, 4, 5, 1, 4, 4, 4])); // 1
console.log(findRotatedMinWithDuplicates([3, 3, 1, 3, 3, 3, 3])); // 1
console.log(findRotatedMinWithDuplicates([3, 3, 3, 3, 3, 1, 3])); // 1
console.log(findRotatedMinWithDuplicates([2, 2, 6, 6, 9])); // 2
console.log(findRotatedMinWithDuplicates([8, 8, 8])); // 8Python
print(find_rotated_min_with_duplicates([4, 4, 5, 1, 4, 4, 4])) # 1
print(find_rotated_min_with_duplicates([3, 3, 1, 3, 3, 3, 3])) # 1
print(find_rotated_min_with_duplicates([3, 3, 3, 3, 3, 1, 3])) # 1
print(find_rotated_min_with_duplicates([2, 2, 6, 6, 9])) # 2
print(find_rotated_min_with_duplicates([8, 8, 8])) # 8The comment after each line is the result you should see.
Common mistakes
- Treating a tie as "go left". Merging the tie into the
hi = midbranch gives the distinct-values code, which returns 3 for[3, 3, 3, 3, 3, 1, 3]. - Moving
loup on a tie. The left end may be the only copy of the smallest value. In[1, 3, 3]the middle ties with the right end;lo++would discard the 1. The tie guarantees a spare copy of the right end's value, so that is the end to drop. - Shrinking both ends on a tie. That is the correct move when searching for a target and all three of left, middle and right are equal, but here only the middle and right were compared. The left end has not been shown to be spare.
- Claiming O(log n). The code looks like a binary search, but an array of equal values takes
n - 1steps. State both the typical and the worst case. - Stripping duplicates first. Removing repeats from both ends before searching does not help: the ties can be in the middle, and the stripping is itself O(n).
Original problem: LeetCode 154: Find Minimum in Rotated Sorted Array II