## Problem Statement

Find Minimum in Rotated Sorted Array II LeetCode Solution – 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:

input : [1,2,3]

output – 1

Explanation :

The minimum element in the nums array is 1.

input : [2,2,2,0,1]

output – 0

Explaination :

The minimum element in nums array is 0. So we return 0.

## Approach:

### Idea

Since the array is sorted one might think of applying a binary search here, but a simple binary search will not work here as the array is rotated as well so we will have to carefully analyze the problem using an example.

**Algorithm-**

- Keep two pointers low and high which points to the lowest and highest boundaries of our search space.
- We then reduce the search space by moving either of the pointers according to various situations.
- If the mid-value is less than the high value then, that means elements lying between mid and high are sorted in non-decreasing order so the
**minimum value will be at the left**, so we do,**high = mid.** - If the mid-value is greater than the high value then, that means elements lying between low and mid are sorted in non-decreasing order so the
**minimum value will be at the right**so we do**low = mid+1.** - If the mid value is equal to the high value then decrease high by 1,
**high = high-1;** - Run the above instructions till low becomes equal to high.

**Inefficient**

**Efficient**

### Example-

nums – [2,2,2,3,4,5,5,5,0,0,1,1,1,1,2,2,2]

**Step -1**

low = 0 , high = 16

mid = (low+high)/2 = 8

now since nums[mid] < nums[high] , so that means we have to move left ,

high = mid;

**step – 2**

low = 0, high = 8;

mid = (low+high)/2 = 4;

nums[mid] > nums[high] , move right,

low = mid+1;

**step – 3**

low = 5 , high = 8;

mid = (5+8)/2 = 6;

nums[mid] > nums[high] , move right,

low = mid+1;

**step – 4**

low = 7 , high = 8;

mid = (7+8)/2 = 7;

nums[mid] > nums[high] , move right,

low = mid+1;

low == high == 8, this is our minimum element’s index,

minimum element = nums[8] = 0;

## Code –

### C++ Code

class Solution { public: int findMin(vector<int>& nums) { int n = nums.size(); int str=0,end=n-1; while(str < end){ int mid = str + (end-str)/2; if(nums[mid] < nums[end]){ end = mid; } else if(nums[mid] > nums[end]){ str = mid+1; } else{ end-=1; } } return nums[str]; } };

### Java code

class Solution { public int findMin(int[] nums) { int low = 0; int high = nums.length - 1; while(low < high){ int mid = (low+high)/2; if(nums[mid] < nums[high]){ high = mid; } else if(nums[mid] > nums[high]){ low = mid+1; } else{ high -= 1; } } return nums[low]; } }

## Time and Space Complexity Analysis for Find Minimum in Rotated Sorted Array II LeetCode Solution

### Time Complexity –

Since we are using a binary search algorithm and reducing the search space by half, the average time complexity is **O(logn)**, but in the **worst case** if all the elements are equal then complexity is **O(n)**.

### Space complexity –

We are not using any extra space here, **Space complexity is O(1)**.