# 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.

### 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*

we follow **condition1**.

*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[0]`

. 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`

.

### 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