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.
At this point we can be sure that the answer is not in the right and side. left side has our answer. So,
if (m < l and m < r): r = m.
This time the answer is to the right. So,
if (m > l and m > r): l = m + 1.
we follow condition1.
We realize that the answer is still to the left, even as
m < l and m == r. The condition 1 is thus modified to:
if (m < l): r = m
similarly in this iteration, we modify the 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
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
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 -= 1all 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.
June 13, 2022
January 24, 2022
January 20, 2022