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.

Problem Overview

Suppose an array of length n sorted in ascending order is rotated between 1 and n times. For example, the array nums=[0,1,2,4,5,6,7] might become:

[4,5,6,7,0,1,2] if it was rotated 4 times.

[0,1,2,4,5,6,7] if it was rotated 7 times.

Notice that rotating an array [a[0],a[1],a[2], ... ,a[n-1]] 1 time results in the array [a[n-1], a[0], a[1], a[2], ... ,a[n-2]].

Given the sorted rotated array nums of unique elements, return the minimum element of this array. You must write an algorithm that runs in O(log(n)) time.

Constraints:

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 nums[0].

Example

Input: nums = [3,4,5,1,2]
Output: 1
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.

Solution Discussion

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.

When 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 nums[0]<nums[len(nums)-1] .

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

How do you determine the inflection point with these pointers?

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?

Using the 3 pointers, how do you decide which side to search next?

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[0] < 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!