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

iteration 1 for general case example
iteration 1 for general case example

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

 iteration 2 of the binary search
iteration 2 of the binary search

This time the answer is to the right. So,

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

iteration 3

 iteration 3 of the binary search
iteration 3 of the binary search

we follow condition1.

iteration 4

iteration 4 of the binary search
iteration 4 of the binary search

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

iteration 5 of the binary search
iteration 5 of the binary search

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:

zoomed in case for the last couple of iterations

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:

worst case time complexity case for "Find Minimum in Rotated Sorted Array"
worst case time complexity case for “Find Minimum in Rotated Sorted Array”

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.


    Leave a Reply

    Your email address will not be published. Required fields are marked *