# Find Minimum in Rotated Sorted Array II
**Difficulty:** HARD
[External](https://leetcode.com/problems/find-minimum-in-rotated-sorted-array-ii)
Canonical: https://scaleengineer.com/dsa/problems/find-minimum-in-rotated-sorted-array-ii
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search)
**Data structures:** Array
**Companies:** [Google](https://scaleengineer.com/companies/google)
---
## Problem
Suppose an array of length `n` sorted in ascending order is **rotated** between `1` and `n` times. For example, the array `nums = [0,1,4,4,5,6,7]` might become:

* `[4,5,6,7,0,1,4]` if it was rotated `4` times.
* `[0,1,4,4,5,6,7]` if it was rotated `7` times.

Notice that **rotating** an array `[a[0], a[1], a[2], ..., a[n-1]]` 1 time results in the array `[a[n-1], a[0], a[1], a[2], ..., a[n-2]]`.

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.

**Example 1:**

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

**Example 2:**

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

**Constraints:**

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

**Follow up:** This problem is similar to [Find Minimum in Rotated Sorted Array](https://leetcode.com/problems/find-minimum-in-rotated-sorted-array/description/), but `nums` may contain **duplicates**. Would this affect the runtime complexity? How and why?

# Approaches
## Linear Scan
This is a straightforward brute-force approach. We can find the minimum element by simply iterating through the entire array and keeping track of the smallest value encountered.
**Time:** O(n) · **Space:** O(1)
**Pros:** Very simple to understand and implement.; Works for any array, not just rotated sorted ones.
**Cons:** Inefficient as it doesn't use the properties of the input array.; Has a time complexity of O(n), which can be improved upon.
### Explanation
The algorithm works by initializing a variable, say `minimum`, with the value of the first element of the array. It then traverses the array from the second element to the end. For each element, it compares it with the current `minimum`. If the current element is smaller, `minimum` is updated. After checking all elements, the `minimum` variable will hold the smallest value in the array. This approach does not take advantage of the fact that the array is a rotated sorted array, but it is guaranteed to be correct.

```java
class Solution {
    public int findMin(int[] nums) {
        if (nums == null || nums.length == 0) {
            return -1; // Based on constraints, this won't be reached.
        }
        
        int minimum = nums[0];
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] < minimum) {
                minimum = nums[i];
            }
        }
        return minimum;
    }
}
```
### Algorithm
- Initialize `minimum` to `nums[0]`.
- Loop through the array from the second element (`i = 1`) to the end.
- Inside the loop, if `nums[i]` is less than `minimum`, update `minimum = nums[i]`.
- After the loop, return `minimum`.

## Modified Binary Search
A more optimized approach is to adapt the binary search algorithm. The standard binary search works on sorted arrays, and we can modify it to handle the rotation and duplicates. The core idea is to intelligently shrink the search space based on comparisons between the middle element and the boundaries.
**Time:** O(log n) on average, O(n) in the worst case · **Space:** O(1)
**Pros:** Significantly more efficient than linear scan on average, with a time complexity of O(log n).; Utilizes the sorted and rotated nature of the array.
**Cons:** The worst-case time complexity degrades to O(n) when many duplicates are present, making it no better than a linear scan in those specific scenarios.; The logic is more complex to implement and reason about compared to a simple loop.
### Explanation
We use two pointers, `left` and `right`, to define our search space, initially covering the whole array. We iterate as long as `left < right`. In each step, we find the middle element `mid`. The main logic revolves around comparing `nums[mid]` with `nums[right]`:

*   If `nums[mid] < nums[right]`: This implies that the segment from `mid` to `right` is sorted. The minimum element cannot be in the `(mid, right]` range because `nums[mid]` is smaller than `nums[right]`. Therefore, the minimum must be in the `[left, mid]` range. We update `right = mid`.
*   If `nums[mid] > nums[right]`: This indicates that the rotation point (and thus the minimum element) is in the right half of the current search space. The segment `[left, mid]` is sorted and all its elements are greater than `nums[right]`. So, the minimum must be in `[mid + 1, right]`. We update `left = mid + 1`.
*   If `nums[mid] == nums[right]`: This is the tricky case introduced by duplicates. We cannot be certain which half contains the minimum. For instance, in `[3, 1, 3, 3]` and `[3, 3, 1, 3]`, `nums[mid]` can be equal to `nums[right]`, but the minimum is in different halves relative to `mid`. In this situation, we can't discard half of the search space. However, we can safely discard the element at the `right` pointer by decrementing `right`. This is safe because even if `nums[right]` was the minimum, `nums[mid]` has the same value, so we are not losing the minimum value from our search space. This step may degrade the performance to linear time in the worst case (e.g., an array of all same elements), but on average, it's much faster.

The loop continues until `left` and `right` converge (`left == right`). The element at this index is the minimum.

```java
class Solution {
    public int findMin(int[] nums) {
        int left = 0;
        int right = nums.length - 1;
        
        while (left < right) {
            int mid = left + (right - left) / 2;
            
            if (nums[mid] < nums[right]) {
                right = mid;
            } else if (nums[mid] > nums[right]) {
                left = mid + 1;
            } else { // nums[mid] == nums[right]
                right--;
            }
        }
        return nums[left];
    }
}
```
### Algorithm
- Initialize two pointers, `left = 0` and `right = nums.length - 1`.
- Loop while `left < right`.
- Calculate the middle index: `mid = left + (right - left) / 2`.
- If `nums[mid] < nums[right]`, it means the right part is sorted and the minimum is in the left part (including `mid`). So, set `right = mid`.
- If `nums[mid] > nums[right]`, it means the pivot is in the right part. So, set `left = mid + 1`.
- If `nums[mid] == nums[right]`, we cannot determine the location of the minimum. To be safe, we reduce the search space by one element from the right: `right--`.
- When the loop ends, `left` and `right` will point to the same index, which holds the minimum element. Return `nums[left]`.

# Solutions
### Java

```java
class Solution {
public
  int findMin(int[] nums) {
    int left = 0, right = nums.length - 1;
    while (left < right) {
      int mid = (left + right) >> 1;
      if (nums[mid] > nums[right]) {
        left = mid + 1;
      } else if (nums[mid] < nums[right]) {
        right = mid;
      } else {
        --right;
      }
    }
    return nums[left];
  }
}

```

### JavaScript

```javascript
/** * @param {number[]} nums * @return {number} */ var findMin = function (
  nums,
) {
  let left = 0,
    right = nums.length - 1;
  while (left < right) {
    const mid = (left + right) >> 1;
    if (nums[mid] > nums[right]) {
      left = mid + 1;
    } else if (nums[mid] < nums[right]) {
      right = mid;
    } else {
      --right;
    }
  }
  return nums[left];
};

```

### CPP

```cpp
class Solution {
public:
  int findMin(vector<int> &nums) {
    int left = 0, right = nums.size() - 1;
    while (left < right) {
      int mid = (left + right) >> 1;
      if (nums[mid] > nums[right])
        left = mid + 1;
      else if (nums[mid] < nums[right])
        right = mid;
      else
        --right;
    }
    return nums[left];
  }
};

```

### Python

```python
class Solution:
    def findMin(self, nums: List[int]) -> int: left, right = 0, len(nums) - 1 while left < right: mid = (left + right) >> 1 if nums[mid] > nums[right]: left = mid + 1 elif nums[mid] < nums[right]: right = mid else: right -= 1 return nums[left]

```