Find Minimum in Rotated Sorted Array (LeetCode #153)

Image by Mae Mu on Unsplash

This article is part of a series from Nathan Thomas, a full stack software engineer working in San Francisco, CA. Other recent articles from him include Building Your Own Bitcoin Node and Maximum Product Subarray.

Introduction

If you’re looking for a quick walkthrough of an optimal solution to the LeetCode Find Minimum in Rotated Sorted Array problem, welcome. 🔥

This is a question in the Blind 75 LeetCode code challenge list, a group of questions put together by a tech lead at Facebook that’s been touted as a really good way to prep for interviews.

Don’t beat yourself up too much if you’re here because it gave you a hard time. Everyone has a hard time with coding challenges sometimes.

With that said, let’s get right into it so you can get your solution.

Initial Setup 👷🏻‍♂️

The first thing we should always try to do is understand all the rules for our challenge before writing a single line of code (see Polya’s Problem Solving Techniques):

1. We’ll be given a list of nums
2. The values will be sorted
3. However, the values may be rotated around the end to the beginning (e.g. [1, 2, 3, 4, 5] may be rotated like [3, 4, 5, 1, 2]) and given to us as the value of nums
4. We must return the minimum value in the list
5. The list of nums length will be 1 <= len(nums) <= 5000
6. All of the integers as values in nums will be unique
7. We must do this in O(log n) time

Whew. That sounds a bit tough, especially if you haven’t seen a problem like this before.

That’s okay. That’s why you’re here with me. We’ll figure it out together.

I’ll be using Python for the answer for this question since it’s a bit like a universal language — whether you prefer JavaScript, Java, Golang, C, or something else, everyone can “kind of” read Python.

We’ll also be jumping straight into an “optimal” solution. If you’re anything like me, you already attempted this problem before searching for an answer. I’m going to make sure you get a good one.

Let’s get started.

Variable Setup and Logic ✅

The thing that really makes this problem go from an easy to a medium level difficulty is that we are supposed to do this in faster than O(n) (linear) time, as the rules state we have to find the numbers in O(log n) time. This means we can’t just can through the list of nums and track the lowest number seen so far.

Fortunately, the rule giving us a time complexity to hit also is a huge hint!

What famous algorithm runs in O(log n) time complexity? That’s right! A binary search!

We’ll be writing a modified binary search today to look through our list of nums to find a minimum.

What do we need to do a binary search? Well, we need multiple pointers with a pivot in between each time to guess a mid-point, compare, and reset our side pointers.

This begs the question of how to decide when to search the left or righthand sides of the pivot we’ll be using in our binary search. For this, we need to learn an important key to all problems that use a sorted and rotated list (remember these rules since they will help you in the future):

1. If the middle pointer (pivot) value of a sorted and rotated list is less than the left pointer value, the smallest number is either the pivot point or in the lefthand side of the list
2. If the middle (pivot) is greater than the lefthand pointer, the smallest number is in the righthand side of the list
3. The smallest number is always a number whose index — 1 value is great than it (e.g. nums = [4, 5, 6, 1, 2, 3] where 1 is the smallest)

For example, let’s say we have a sorted and rotated list that looks like:

nums = [6, 7, 1, 2, 3, 4, 5]

Notice that the middle point, 2, is less than the lefthand pointer and how it indicates the minimum (which is 1) is in the lefthand side?

Now, notice what happens if we rotate this same list even more:

nums = [4, 5, 6, 7, 1, 2, 3]

With a mid-point of 7, our minimum number is now reliably in the righthand side of the list. You can try playing around with this list (or a different list), and the outcome will always be the same — the mid-point decides whether you need to look in the left or righthand sides for the minimum number.

If you remember this rule for all sorted and rotated-type of problems, you’ll likely be able to come up with solid approaches even if you have to modify up the way you’re doing your final search.

There we go. I think we have a route to move forward now. Let’s go ahead and set up our initial variables:

We will start our left pointer at the 0 index and our right one at the final index of the list of nums.

Notice that we also added an if statement here. That’s because our list of nums has a potential minimum length of 1. If that’s the case, things might get a little messy, right?

Instead, we’ll just send that value back since it’s obviously the minimum value in a list of length 1.

From here, we can get started building our for loop!

Building Our Loop 🔁

We’ll use a while loop for this process since we would want to continue iterating while our left variable is less than our right one (just like a normal binary search).

Additionally, we’ll want (for every iteration of our loop) to pick a pivot point in the middle of the current list to do our comparison. In order to reliably choose this pivot for future iterations when our left and right pointers have been updated, we’ll want to subtract the left value from right, do floor division by 2 (Python allows floor division with the // operator), and then add the left value back.

This is what that looks like:

The next thing we need to do is build some if / else statements that check if we’ve found the minimum number here (or else update our pointers).

This is where the logic we talked about earlier in this article comes in. It turns out that the minimum number will always be when position i is less than i — 1. This makes sense, right? If we have a list like this:

nums = [4, 5, 6, 7, 1, 2, 3]

The minimum number, 1, is the only number where it’s less than the number immediately before it.

We can take advantage of this to write our checks like this:

We take our pivot and check:

1. If the number after pivot is less than pivot (which means the number after pivot is the minimum)
2. If the number before pivot is greater than pivot (which means pivot is the minimum)

If either of those are True, we return the correct minimum number.

If neither of them are True, we update the right pointer to be the pivot if the pivot index value is less than the right pointer. Remember our earlier discussion about finding the minimum when a sorted list is rotated?

If that isn’t true, we will fallback to updating our left pointer to be the pivot.

There we go. That gives us a final algorithm. There’s lots of little things you can do to simplify the syntax for this, but I did my best to make it super clear what was going on when I wrote it out here.

This solution will run in O(log n) time complexity and O(1) space complexity since we always use the same amount of pointer variables.

Conclusion

Congrats 🎉

I know this one was a bit long, but hopefully you feel much more confident approaching problems of this nature now!

Keep an eye out for the rest of these Blind 75 coding challenges articles from me. I’m going to be solving them and publishing these as I go.

Also, feel free to reach out to me on any of the links below if you want to talk about coding, cool tech, or anything else (I really, really like book recommendations).

Thanks for reading!

Nathan

(GitHub, LinkedIn, Twitter, and Personal Site)