Find Minimum in Rotated Sorted Array II — Medium Problem & Solution

nums was sorted in non-decreasing order and then rotated at some pivot. Duplicates are allowed. Return its minimum element.

Difficulty: Medium
Topics: Arrays, Binary Search
Asked at: Amazon, Google, Goldman Sachs
Time limit: 2 s
Memory limit: 256 MB
Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

nums was sorted in non-decreasing order and then rotated at some pivot. Duplicates are allowed.

Return its minimum element.

Example 1

Input: nums = [1,3,5]
Output: 1
Explanation: Rotated zero times.

Example 2

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

Example 3

Input: nums = [3,3,1,3]
Output: 1
Explanation: The duplicated 3s hide the pivot from a naive comparison.

Constraints

1 <= nums.length <= 5000
-5000 <= nums[i] <= 5000
nums is a rotation of a non-decreasing array.

How to solve Find Minimum in Rotated Sorted Array II

Anchor the comparison at the right end. A midpoint greater than the right end must sit in the left, higher run, so the minimum lies after it; a smaller midpoint could itself be the minimum. Equality gives no information, and the only safe move is to discard one candidate.

Approach

While lo < hi, take mid.
nums[mid] > nums[hi] → lo = mid + 1.
nums[mid] < nums[hi] → hi = mid.
Otherwise hi--.

Why it works

Comparing against nums[hi] is what makes the rule total: in a rotated non-decreasing array, everything strictly greater than the last element belongs to the pre-pivot run. Shrinking hi on equality is safe because nums[hi] is duplicated at mid, so discarding it cannot remove the only copy of the minimum. That step is what pushes the worst case to O(n) for inputs like [1,1,1,1].

Complexity

Time — O(log n) average, O(n) worst case
Space — O(1)

Pitfalls

Comparing with nums[lo] instead needs extra cases and gets [3,3,1,3] wrong.
Setting hi = mid - 1 in the second branch can skip over the minimum.
hi-- rather than lo++ on equality — dropping from the left can discard the pivot itself.

Reference solution

Python

from typing import List

def findMin(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]

JavaScript

var findMin = function(nums) {
    var lo = 0, hi = nums.length - 1;
    while (lo < hi) {
        var mid = (lo + hi) >> 1;
        if (nums[mid] > nums[hi]) lo = mid + 1;
        else if (nums[mid] < nums[hi]) hi = mid;
        else hi--;
    }
    return nums[lo];
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 667 arrays problems · the whole catalogue