# Find Minimum in Rotated Sorted Array II | Solution Explained

What makes LeetCode 154. Find Minimum in Rotated Sorted Array II fun is the optimized solution. I explain the binary search optimization in detail. Problem Link.

## 0. Find Minimum in Rotated Sorted Array: Dumb Solution

A possible solution to this questions is to simply return the `min(a)`. This solution is not fun and the interviewer will most likely ask you to think of an optimized solution.

```class Solution:
def findMin(self, a: List[int]) -> int:
return min(a)```

## 1. Find Minimum in Rotated Sorted Array: Observations

### 1.0. How to think about the optimization?

Before we talk about optimizations, we re-read the question. The input is a rotated sorted array. This makes us think of binary search. However, the array is rotated. So how will binary search even work? Below is a visual representation of how the array may look visually. a visual representation of the general case for “Find Minimum in Rotated Sorted Array” problem

### 1.1. How to start implementation?

Since we want to think about binary search, let’s start from the official Python3.9 implementation.

```lo = 0
hi = len(a)
# x is the target

while lo < hi:
mid = (lo + hi) // 2
if x < a[mid]:
hi = mid
else:
lo = mid + 1
```

The only thing we don’t have is x. In fact, that is exactly what we are looking for.

### 1.2. How to find x?

Time to start thinking about core observations. Let’s create left, right and mid pointers, and start.

Iteration 1

At this point we can be sure that the answer is not in the right and side. left side has our answer. So,

condition1: `if (m < l and m < r): r = m`.

iteration 2

This time the answer is to the right. So,

condition2: `if (m > l and m > r): l = m + 1`.

iteration 3

iteration 4

We realize that the answer is still to the left, even as `m < l and m == r`. The condition 1 is thus modified to:

condition1: `if (m < l): r = m`

iteration 5

similarly in this iteration, we modify the condition2.

condition2: `if(m > r): l = m + 1`

Finally, both the conditions are:

```if a[m] < a[l]: r = m
elif a[m] > a[r]: l = m + 1```

last iterations

towards the last iteration, we will have something of the sort:

In this case, we want to continually move the right by the slightest amount, 1. Finally, we can summarize the logic in the code below.

## 2. Find Minimum in Rotated Sorted Array: Code

### 2.0. Code

```class Solution:
def findMin(self, a: List[int]) -> int:
l, r = 0, len(a)-1
while l < r:
m = (l + r)//2

if a[m] < a[l]:
r = m
elif a[m] > a[r]:
l = m + 1
else:
r -= 1
return a[l]
```

### 2.1. Complexity Analysis

• Time: O(logN) average case. Worst case is when the array is not rotated, so we continually do `r -= 1` all the time.
• Time: O(N) worst case.
• Space: O(1) in worst case, since we only ever store the pointers – left, right and mid.

The worst case time complexity demands more explanation. Take a look at the case:

In this case, we do not have a rotated array. We only have a sorted one. So the answer is `a`. Easy, right? Well from our (modified) condition1 and condition2, we observe how both of them are not followed. We have to follow the condition3, which says to do `r -= 1`. For an array of length `n`, that all of a sudden means that we have to do this operation `O(N)` times, till we finally have `l == r`, where l never got updated, and was `l = 0`.

##### Tanishq Chaudhary Producing high-quality intuitive explanations of interview problems. Currently covering LeetCode and InterviewBit.

### Recommended Posts

##### Gas Station | InterviewBit | Solution Explained

June 13, 2022

##### Reverse integer | InterviewBit | LeetCode | Solution Explained

January 24, 2022

##### Furthest Building You Can Reach | LeetCode | Solution Explained

January 20, 2022

This site uses Akismet to reduce spam. Learn how your comment data is processed.