Skip to main content

154. Find Minimum in Rotated Sorted Array II

hard

Same problem as part I but duplicates are allowed. That one change pushes the worst case from O(log n) to O(n) and forces a careful tiebreak rule — a favorite interview gotcha.

By Sam K., Founder, InterviewChamp.AI · Last verified

Problem

Suppose an array of length n sorted in ascending order is rotated between 1 and n times. Given the sorted rotated array nums that may contain duplicates, return the minimum element of this array. You must decrease the overall operation steps as much as possible.

Constraints

  • n == nums.length
  • 1 <= n <= 5000
  • -5000 <= nums[i] <= 5000
  • nums is sorted and rotated between 1 and n times.

Examples

Example 1

Input
nums = [1,3,5]
Output
1

Example 2

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

Example 3

Input
nums = [10,1,10,10,10]
Output
1

Explanation: Duplicates at the boundary force a worst-case linear scan.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Without duplicates you compare nums[mid] with nums[hi] and pick a side. Duplicates break that test when nums[mid] == nums[hi].

Hint 2

When nums[mid] == nums[hi], you can't tell which half holds the minimum. The only safe move is hi -= 1 (shrink one step).

Hint 3

Worst case (all duplicates) degrades to O(n), but the average case stays O(log n).

Solution approach

Reveal approach

Modified binary search comparing nums[mid] with nums[hi]. Initialize lo = 0 and hi = n - 1. While lo < hi, compute mid = lo + (hi - lo) / 2. Three cases: (1) nums[mid] > nums[hi] — the minimum is strictly to the right of mid, so lo = mid + 1. (2) nums[mid] < nums[hi] — mid is in the same sorted segment as hi and the minimum is at mid or to the left, so hi = mid. (3) nums[mid] == nums[hi] — we can't distinguish the rotated segments, but we can safely drop hi without missing the minimum (nums[mid] is still a candidate at index mid), so hi -= 1. When lo == hi, return nums[lo]. The Case 3 step is what costs us the O(log n) guarantee: an adversarial input of all duplicates with the minimum hidden at one end forces n iterations. Average case remains O(log n), worst case O(n), space O(1). The tiebreak hi -= 1 (not lo += 1) is critical — going from the lo side could skip past the minimum.

Complexity

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

Related patterns

  • binary-search
  • modified-binary-search

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Google
  • Microsoft

More Binary Search practice problems

See all Binary Search problems →