Solution: Find Minimum in Rotated Sorted Array II

Statement

Imagine you have an array, nums, of length $n$ that was originally sorted in non-decreasing (ascending) order. This array has been rotated between $1$ and $n$ times. For example, the sorted array $[0,2,3,3,5,7,11]$ can become:

• $[5,7,11,0,2,3,3]$, if rotated $3$ times

• $[0,2,3,3,5,7,11]$, if rotated $7$ times

A single rotation moves the last element to the front. So, if the original array is $[a[0], a[1], ..., a[n-1]]$, rotating it once produces $[a[n-1], a[0], a[1], ..., a[n-2]]$.

You are given a sorted, rotated array, nums, that may include duplicate elements. Your job is to return the minimum element in the array.

Constraints:

• $n ==$ nums.length

• $1 \leq n \leq 1000$

• $-1000 \leq$ nums[i] $\leq 1000$

• nums is sorted and rotated between $1$ and $n$ times.

Solution

The solution’s essence lies in leveraging a modified binary search to efficiently locate the minimum element in a rotated sorted array, even in the presence of duplicates. The algorithm defines a search boundary using low and high pointers, representing the current range where the minimum element could exist. A third pivot pointer is calculated to point to the middle element of the current search space.

By comparing the element at pivot with the element at high, the algorithm determines whether the minimum lies in the left or right half of the current search space and updates the boundaries accordingly. Specifically, it handles the following three cases:

• Case 1 (nums[pivot] < nums[high]): The pivot element lies in the same half as the upper bound. This means the minimum is to the left of or at the pivot. Therefore, we move high to pivot.

• Case 2 (nums[pivot] > nums[high]): The pivot element lies in a different half from the upper bound. Hence, the minimum must lie to the right of pivot, and we move low next to pivot.

• Case 3 (nums[pivot] == nums[high]): It’s ambiguous which half contains the minimum. To avoid skipping the minimum or falling into an infinite loop, we safely reduce the upper bound (high) by one. This step ensures progress and correctness without eliminating any possible minimum.

Using the intuition above, we implement the algorithm as follows:

1. Set two pointers: low at the beginning of the array and high at the end. These pointers define the current search space.

2. Iterate through the array as long as low < high:

   1. Compute the middle index, pivot, of the current search space.

   2. If the element at pivot is less than the element at high, the minimum could be at pivot or anywhere to the left, so shrink the search space by setting high = pivot.

   3. On the other hand, if the element at pivot is greater than the element at high, the minimum must lie to the right of pivot. Therefore, update the low pointer to pivot + 1.

   4. Finally, if both values are equal, we can’t determine which side the minimum is on (due to duplicates). Safely reduce the search space by reducing high by one.

3. When the loop terminates, low points to the minimum element. Return the value at index low, representing the minimum element in the rotated sorted array.

Let’s look at the following illustration to get a better understanding of the solution: