Leetcode 153 — Find Minimum in Rotated Sorted Array
Today’s article will cover and explain the optimal solution to Leetcode 153 — Find Minimum in Rotated Sorted Array.
Suppose an array of length
nsorted in ascending order is rotated between
ntimes. For example, the array
[4,5,6,7,0,1,2]if it was rotated
[0,1,2,4,5,6,7]if it was rotated
Notice that rotating an array
[a,a,a, ... ,a[n-1]]1 time results in the array
[a[n-1], a, a, a, ... ,a[n-2]].
Given the sorted rotated array
numsof unique elements, return the minimum element of this array. You must write an algorithm that runs in
1 <= n <= 5000
-5000 <= nums[i] <= 5000
All the integers of nums are unique
nums is sorted and rotated between 1 and n times
The constraints are important here, in this case they’re giving us some very useful information to make assumptions from. The obvious bit is handling the trivial case where
len(n) == 1 should be accounted for. Next, knowing all the elements are unique gives us assurance that there is a solution, and only 1 solution. Finally, we’re given information of another trivial case, one covered in the problem description; that is, if the array is rotated
n times, it is equivalent to the original array. In otherwords,
sorted(nums) == rotated(sorted(nums), len(nums)) , and in that case we’d know the minimum number is
Input: nums = [3,4,5,1,2]
Explanation: The original array was [1,2,3,4,5] rotated 3 times.
The example doesn’t really give us much. It’s mostly a sanity check.
As I mentioned in my comments after the Problem Overview, there are two simple ‘base’ cases that we can get out of the way from the get go:
Let’s take a look at this for a second. If
nums is a single element, it is by definition of being the only element, the minimum. Okay, case handled.
len(nums)>= 2 we now have to find the min. But what do we know from the overview? We know that the array is 1) sorted (strictly increasing left to right) and 2) rotated 1 to n (
n == len(nums)) times, and rotating an array n times is equivalent to not rotating the array at all. So, given those bits of info, we check that case with
Modified Binary Search
With those two easy cases checked, we now know that our array is rotated in such a way that we’re going to need to iterate over it to find the min. This problem is set up to utilize a binary search. Divide and conquer this array.
Before we get to that point, I first want to point out a key concept to understanding the solution. When an array is sorted in ascending order (this case), the elements are strictly increasing. Meaning,
num[i] < num[i+1] always. Once the array is rotated, there exists some point that violates that condition. For example:
[5, 6, 7, 1, 2, 3] was rotated and at index
3 the array decreases before resuming it’s increasing behavior. The point where the array decreases, or ‘resets’, is the inflection point.
Then, let me pose a question to you: How do you identify the minimum value if middle was at one of these positions (for example):
This introduces us to how we identify that minimum value. Different from a normal binary search where we check
nums[mid]==target , we need to check is mid on the inflection point, and if so, is it the minimum or the maximum? We do this with the following code:
So, we’ve figured out our equivalent to checking if
nums[mid] is the target. Next, is how do we determine which side to divide and conquer to? In a normal binary search, we simply check
target < nums[mid] to know if target is on the left or right side of the middle. In this problem, it is a bit different. Using the examples below, I pose this question: How do you determine which side to search?
Let’s begin with case 2 because it is the easier of the 2 to follow. If you answered check
nums[left] < nums[mid] you’d be correct! Notice, we know our array is only increasing on the left side by nature of
nums[mid] remaining greater than all to it’s left.
In the same thought idea, case 1, checks if
nums[left] > nums[mid] indicating that the inflection point is on the left hand side.
Note: You can also check if
nums < nums[mid] because it implies the same property that what is on your left must be strictly and always increasing for the middle to be larger (property of the array being sorted).
Putting it all together, we have the following solution:
I hope you enjoyed the article! Thanks for reading!