HardArrayBinary Search

Find Minimum in Rotated Sorted Array II

1 approach, code in every language

An array that was originally sorted in ascending order has been rotated at some unknown pivot, and the array may contain duplicate values. After the rotation, find the smallest element in the array.

The presence of duplicates is what makes this variant harder: when the middle value ties with the boundary value, you cannot tell which half holds the minimum, so the search must degrade gracefully in those ambiguous cases.

Example 1

Input: nums = [4, 5, 6, 6, 1, 2, 3]

Output: 1

The array was rotated so that the ascending run wraps around; the smallest value sitting at the rotation point is 1.

Example 2

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

Output: 1

Duplicates surround the pivot, but narrowing the window carefully still isolates the minimum value of 1.

Constraints

1 <= nums.length <= 5 * 10^4
-10^4 <= nums[i] <= 10^4
nums is a rotation of an array sorted in ascending order
nums may contain duplicate values

Binary Search with Duplicate Handling

Compare the middle element against the right boundary and shrink the search window, stepping the boundary inward by one when the two tie.

Loading animation…

Intuition

Compare the middle value with the value at the right edge of the current window. If the middle is larger, the rotation point (and therefore the minimum) must be to the right of mid, so move lo past mid. If the middle is smaller, the minimum is at mid or to its left, so pull hi down to mid. The tricky case is when they are equal: you cannot decide which side holds the minimum, but dropping the right boundary by one is always safe because an identical value still exists at mid, so no candidate minimum is lost.

Algorithm walkthrough

1Initialize lo = 0 and hi = n - 1 to cover the whole array.
2While lo < hi, compute mid and compare nums[mid] with nums[hi].
3If nums[mid] > nums[hi], the minimum lies to the right, so set lo = mid + 1.
4If nums[mid] < nums[hi], the minimum is at or left of mid, so set hi = mid.
5If they are equal, decrement hi by one to safely shrink the window, then continue; when lo == hi, nums[lo] is the answer.

Implementation

from typing import List


class Solution:
    def findMin(self, nums: List[int]) -> int:
        lo, hi = 0, len(nums) - 1
        while lo < hi:
            mid = (lo + hi) // 2
            if nums[mid] > nums[hi]:
                lo = mid + 1
            elif nums[mid] < nums[hi]:
                hi = mid
            else:
                hi -= 1
        return nums[lo]

Time

O(log n) average, O(n) worst case

Space

O(1)

When many duplicates force the equal-value branch, the window shrinks one step at a time, degrading to linear time.

Create a free account to see the solution

You get the step-by-step animation, the intuition and clean code in every language. Free, no credit card.

Create a free account Already have an account? Sign in

Back to Binary Search

After the pattern

Now solve one you haven't seen.

Lowest Reading On A Turned Drum is our own problem on the technique behind Find Minimum in Rotated Sorted Array II: a new statement, so there's no answer to remember. Write it in your browser and run it against graded tests.

Practise it with tests All practice problems

1,194 problems · 15,062 graded tests · free