Search in Rotated Sorted Array (LeetCode #33)

Image by Markus Winkler 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 Search in Rotated Sorted Array problem, you’re in the right place. This one is very similar to Find Minimum in Rotated Sorted Array, so you might want to do that one first to better understand this problem.

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

I’m going to teach you a formula that will let you solve it immediately from here on out!

Understanding the Problem 👷🏻‍♂️

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 an list of nums in ascending order (with distinct values)
2. The order of nums might be rotated (e.g. [5, 6, 7, 1, 2, 3] instead of [1, 2, 3, 5, 6, 7]
3. We’ll be given the list after it’s rotated
4. We should search for a target number in the list
5. If we find it, return the index of target
6. If we don’t find it, we should return -1
7. nums will have a length of 1 <= len(nums) <= 5000
8. We must write an algorithm with a time complexity of O(log n)

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.

That’s good enough to kick this whole thing off. Let’s go ahead and get started!

Variable Setup 🏆

As I said up above, this problem is very similar to Find Minimum in Rotated Sorted Array. I’d recommend you do that one first if you haven’t already.

While the rule about achieving a time complexity of O(log n) seems hard at first glance, it’s actually the biggest hint we have. What type of search runs in O(log n)?

That’s right!

We’ll be doing a Binary Search!

However, the first thing we need to do is to set up our initial variables:

The if statement here is just to catch instances where we have a list of length 1 but that value is what we’re looking for. It wouldn’t be caught by the binary search we’ll be doing (you’ll see why in a minute).

In true binary search form, we’re setting up two initial pointers for the start and end of our list that we’ll then update them as we do our search.

Building Our Loop 🔁

The next stage of this problem is to build out our while loop. We’ll continue searching as long as left is less than right.

To facilitate our search, we’ll also need to choose a pivot value every single iteration of our loop.

This is what that looks like in code form:

Notice with the pivot value that we have to subtract left from right before we divide and then add left back afterwards. This is to account for situations when we’ve already updated left to be greater than 0.

Also, the // operator is just Python’s way of doing floor division (e.g. rounding down to the closest whole integer after dividing).

Exit Cases and Pointer Movement 💯

Now that we have our left, pivot, and right pointers all set up along with our loop, we can actually get down to the searching aspects of this coding challenge.

The first thing we need to do is check to see if (for every iteration of our loop) the left, pivot, or right pointers are the target value that we’re searching for:

First, we’ll check if left is target. Then we do the same with right and finally with pivot. Finally, we have a break in place to see if the pointers are next to each other but didn’t return any value; this situation means that the value does not exist in the list and could otherwise send us into an infinite loop.

These all run in constant time each time our list runs, so we’re essentially able to check 3 pointers on the list every time the loop runs. 🎉

Nice, right?

The final thing we need to do is to decide how to update our left and right pointers.

But before we do that, 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 greater 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 check 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” types 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.

With this in mind, we can write our code like this:

Notice that we’ve added two root if / else statements. These are essentially comparing our pivot point against the numbers in the list using the rotated and sorted list rules we discussed above.

This is the decision tree for them:

1. If nums[pivot] point is less than nums[right]:

• If nums[pivot] is less than target and target is less than nums[right], set left equal to pivot
• Else, set right equal to pivot

2. Else (if nums[pivot] point is greater-than nums[right]):

• If nums[right] is less than target and target is less than nums[pivot], set right equal to pivot
• Else, set left equal to pivot

This will all run in our loop and eventually either return our number in nums or break out of the loop. If we break out, we should return -1 at the bottom of the function.

This entire algorithm will run in O(log n) time complexity (since it’s a binary search) with O(1) space complexity (since we’re only using a few variables to track our pointers).

Conclusion

There we go. I hope this helped you out!

Keep an eye out for the rest of these Blind 75 coding challenges articles. It’s going to be a fun ride.

Feel free to reach out (using the links below) if you want to talk about coding, cool tech, or anything else (I really like book recommendations).

Thanks for reading. 🔥

Nathan

(GitHub, LinkedIn, Twitter, and Personal Site)