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 Alex Chen, 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

Practice these live with InterviewChamp.AI

Drill Find Minimum in Rotated Sorted Array II and Binary Search problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →