Find Minimum in Rotated Sorted Array

Q: What is the time complexity of finding the minimum in a rotated sorted array?

O(log n) time and O(1) extra space with binary search, at most 13 comparisons for 5000 elements. The walk to the drop is O(n) : it reads every element when the minimum sits at the end.

Q: Why compare nums[mid] with nums[hi] and not with nums[lo]?

nums[hi] always settles which side the minimum is on. With nums[lo] , the result nums[mid] > nums[lo] fits both an unrotated range, where the minimum is nums[lo] , and a rotated one, where it lies right of mid .

Q: How do you find how many times a sorted array was rotated?

Run the same binary search and take lo , the index of the minimum. If a rotation moves the last element to the front, that index is the count. If it moves the first element to the back, as here, the count is (n - lo) mod n : 7 minus 4 gives 3 in the first example.

Q: Does the binary search work when the array has duplicates?

Not unchanged. In [2, 2, 2, 0, 2] , nums[mid] can equal nums[hi] , which rules out neither side. Setting hi = hi - 1 then is safe, because a copy of nums[hi] stays in range, but the worst case becomes O(n) .

MediumBinary search

+10

A list of distinct integers was sorted in increasing order and then rotated: some number of elements, possibly zero, were taken from the front and moved to the back in the same order. For example, [2, 5, 9, 11, 13, 15, 17] rotated by 3 becomes [11, 13, 15, 17, 2, 5, 9]. You get the rotated list nums. Return its smallest value in O(log n) time.

Function

findMin(nums: integer-array) → integer

numsinteger-array: the rotated sorted list of distinct integers
Returnsinteger: the smallest value in nums

Constraints

1 ≤ nums.length ≤ 5000
-10⁴ ≤ nums[i] ≤ 10⁴
All values in nums are distinct.
nums is an increasing list rotated by some k with 0 ≤ k < nums.length; k = 0 leaves it unrotated.

Examples

Input: nums = [11, 13, 15, 17, 2, 5, 9]
Output: 2
Explanation: The values climb to 17 and fall to 2. Since 17 > 9, the minimum is right of index 3; then 5 ≤ 9 and 2 ≤ 5 pull hi back to index 4, which holds 2.

Input: nums = [4, 7, 10, 12]
Output: 4
Explanation: This list was rotated by 0, so it is still sorted and the minimum is its first value. Every middle value is at most the last one, so hi keeps moving left until it reaches index 0, which holds 4.

Input: nums = [30, -6, 0, 8, 19]
Output: -6
Explanation: Rotating by 4 puts the largest value, 30, first and the minimum, -6, at index 1. The search narrows to indexes 0 and 1, sees 30 > -6, and moves lo to 1.

Follow-up

Can you return the k-th smallest value of nums in O(log n) time, without sorting it?

Hints

Open them one at a time. Each one gives away a little more.

0 of 3 opened

Solution

A rotated sorted list is two increasing runs, and the minimum starts the second one, right after the only place where the values go down. Comparing a middle value with the last value of the range tells you which side of that drop the middle is on, so binary search finds it in O(log n).

Walk until the values drop

Intuition

Rotation keeps both runs sorted and creates one place where a value is smaller than the one before it: the largest value followed by the smallest. Walk from left to right and return the first such value. If there is none, the list was not rotated and the minimum is nums[0].

The drop can be anywhere. When the rotation moved one element, as in [2, 3, 4, 5, 6, 7, 8, 1], the walk reads the whole list: 5000 comparisons for 5000 elements, where binary search needs 13.

Algorithm

For each index i from 1 to n-1, compare nums[i] with nums[i-1].
If nums[i] < nums[i-1], return nums[i]: the second run starts there.
If the loop ends, the list was not rotated: return nums[0].

def findMin(nums):
    for i in range(1, len(nums)):
        if nums[i] < nums[i - 1]:
            return nums[i]  # the only drop: the second run starts here
    return nums[0]  # no drop: the list was not rotated

Binary search against the last value

Intuition

Keep one promise: the minimum lies between lo and hi, inclusive. Compare the middle value with nums[hi], the last value of the range.

If nums[mid] > nums[hi], the values go down somewhere between mid and hi, and the minimum comes right after that drop, so set lo = mid + 1. Otherwise nums[mid] < nums[hi], since the values are distinct, so nums[mid..hi] climbs with no drop in it. The minimum is nums[mid] or something before it: set hi = mid, keeping mid in range. Either move keeps the promise and shrinks the range, so when lo meets hi the one value left is the minimum.

Each step halves the range: at most 13 steps for 5000 elements, with two indexes of extra memory.

Algorithm

Set lo = 0 and hi = n-1.
While lo < hi, compute mid = lo + (hi - lo) / 2.
If nums[mid] > nums[hi], set lo = mid + 1.
Otherwise set hi = mid.
When the loop ends, return nums[lo].

def findMin(nums):
    lo, hi = 0, len(nums) - 1  # the minimum sits in nums[lo..hi]
    while lo < hi:
        mid = (lo + hi) // 2
        if nums[mid] > nums[hi]:
            lo = mid + 1  # the values drop after mid, so the minimum is right of it
        else:
            hi = mid      # nums[mid..hi] climbs: the minimum is at mid or left of it
    return nums[lo]

Pitfalls and edge cases

Writing hi = mid - 1 in the second branch. In [3, 1, 2] the middle value 1 is not above 2, so hi drops to 0 and the function returns 3.
Looping on lo ≤ hi. Once lo equals hi, hi = mid changes nothing and the loop never ends.
Comparing with nums[lo] instead of nums[hi]. In the unrotated [1, 2, 3, 4, 5], the middle value 3 is above nums[0] = 1, so the search moves right and returns 4.
Giving the walk no fallback for an unrotated list. In [4, 7, 10, 12] nothing drops, so return nums[0].

Frequently asked questions4

What is the time complexity of finding the minimum in a rotated sorted array?

O(log n) time and O(1) extra space with binary search, at most 13 comparisons for 5000 elements. The walk to the drop is O(n): it reads every element when the minimum sits at the end.

Why compare nums[mid] with nums[hi] and not with nums[lo]?

nums[hi] always settles which side the minimum is on. With nums[lo], the result nums[mid] > nums[lo] fits both an unrotated range, where the minimum is nums[lo], and a rotated one, where it lies right of mid.

How do you find how many times a sorted array was rotated?

Run the same binary search and take lo, the index of the minimum. If a rotation moves the last element to the front, that index is the count. If it moves the first element to the back, as here, the count is (n - lo) mod n: 7 minus 4 gives 3 in the first example.

Does the binary search work when the array has duplicates?

Not unchanged. In [2, 2, 2, 0, 2], nums[mid] can equal nums[hi], which rules out neither side. Setting hi = hi - 1 then is safe, because a copy of nums[hi] stays in range, but the worst case becomes O(n).

def findMin(nums):
    # Write code here

Test #1

Test #2

Test #3

Argument

nums = [11, 13, 15, 17, 2, 5, 9]

Expected Output