LeetCode 153: Find Minimum in Rotated Sorted Array

Problem

This is a JavaScript solution for LeetCode problem 153.

Tip

Before starting I think it’s worth point out some tips to give perspective on the problem and potential solutions.

• Another way to phrase this problem is “find the smallest value in the array”. This is because the smallest value in the array will always be the point at which the rotation starts, and thus the answer.
• Finding “minimum”, “maximum”, “target” can be done in O(n).
• If the array is rotated the left side will exclusively be larger than the right side.
• The problem ask for a solution in O(log n) which means we’ll need to use an algorithm like binary search.

Solution

time: O(log n)
space: O(n)
type: binary search

If the array is rotated we will have two sub arrays of sorted values. Having two halves means that we can think of this as a divide and conquer problem. Binary search works great for these kinds of problems.

A binary search will allow us to divide the array into smaller and smaller sub arrays, eventually finding the position where the pivot is more than the element to its right, indicating that the immediate element to the right is lowest element in the array.

We’ll also need to create a mutable variable to store the lowest pivot we’ve found so far. We’ll call this pointOfRotation. The initial value for this will be the first item in the array. We’ll also need to set up the left and right pointers for our binary search.

Our while condition needs to also have an equality check for the case where our array has only one values. When the array only has one value, both of left and right pointers will equal 0, meaning that the while loop will not check a single value, which could be our target.

There are two objectives we need to consider inside of our while loop. The first is our success condition, and the second is knowing when and how to adjust the boundaries of the pointers.

For the success condition, if all elements in the array is tested and the pivots are not found to be greater than the element to its right, then the number of rotations in the array is 0, indicating that the array is sorted. In this case, we return the first element of the array, as this indicates the start of the sorted array, and thus its lowest value.

The second objective is to check the conditions on which we need to update the pointers. This is important as it will allow us to divide the array into smaller and smaller subarrays until we find the at which the value stop ascending.

We will know we’ve found the point of rotation if the element immediately to the right of the pivot is less than the pivot. This is correct because in a sorted array, a number to the left cannot be greater than a number on the right.

That’s it. You can find the code here on GitHub.

You can read on for the brute force solution O(n).

Brute force

time: O(n)
space: O(1)
type: brute force

A bruce force approach can be used with a O(n) by looping through the entire array and keeping a track of the lowest value seen, and returning this value at the end.

That’s it. You can find the code here on GitHub.