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.

Tanishq Chaudhary

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