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. Each step keeps one half of the range, so a list of 5000 elements needs at most 13 comparisons. The scan for 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]?

Because nums[hi] always settles which side the minimum is on, and nums[lo] does not. If nums[mid] > nums[hi] , the values must fall between mid and hi ; otherwise nums[mid..hi] climbs and the minimum is at mid or before it. With nums[lo] , the result nums[mid] > nums[lo] fits both an unrotated list, 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 return lo , the index of the minimum, instead of nums[lo] . If you count a rotation as moving the last element to the front, that index is the rotation count. If you count it as moving the first element to the back, as this problem does, the count is (n - lo) mod n : in [11, 13, 15, 17, 2, 5, 9] the minimum is at index 4, and 7 minus 4 gives the 3 values moved.

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] , and then neither side is ruled out. Shrinking with hi = hi - 1 in that case is safe, because a copy of nums[hi] stays in range at mid , but a list of equal values with one smaller value hidden among them then costs 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 from 11 to 17 and then fall to 2, where the second run starts. The search sees 17 > 9 at index 3, so the minimum is to its right; then 5 ≤ 9 and 2 ≤ 5 pull hi back until the range is index 4 alone, 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: Four values were moved from the front to the back, so the largest value, 30, now comes first and the minimum, -6, sits at index 1. The search shrinks the range to indexes 0 and 1, sees 30 > -6, and moves lo to 1.

+17 hidden tests on Submit

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, [11, 13, 15, 17] and then [2, 5, 9]. The minimum is the first value of the second run, right after the only place where the values go down. Walking the list finds that drop in O(n). Comparing one middle value with the last value of the range tells you which side of the drop the middle is on, so binary search finds it in O(log n).

Walk until the values drop

Intuition

In a sorted list each value is larger than the one before it. Rotating the list keeps both runs sorted and creates exactly one place where that fails: the largest value followed by the smallest. So walk from left to right and return the first value that is smaller than its neighbour on the left. If no such value exists, the list was rotated by 0 and the minimum is nums[0].

In [11, 13, 15, 17, 2, 5, 9] the walk passes 13, 15 and 17, each above the value before it, and stops at index 4, where 2 is below 17. This is already better than taking the minimum of every value, because it stops at the drop, but 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. At the start that range is the whole list. Look at the middle value and compare it 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 is the value right after that drop, so it is right of mid: set lo = mid + 1. Otherwise nums[mid] < nums[hi] (the values are distinct), so nums[mid..hi] climbs with no drop in it. The minimum is then nums[mid] or something before it, so set hi = mid. Do not skip past mid: it may be the minimum. Either move keeps the promise and shrinks the range, and when lo meets hi the one value left is the minimum.

Trace the first example, [11, 13, 15, 17, 2, 5, 9]. The range 0 to 6 has middle 3, value 17, above nums[6] = 9, so lo becomes 4. The range 4 to 6 has middle 5, value 5, not above 9, so hi becomes 5. The range 4 to 5 has middle 4, value 2, not above 5, so hi becomes 4. Return nums[4] = 2.

Each step halves the range, so the loop runs at most about log2(n) times: 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

The loop is four lines long, and each line has a tempting wrong version.

Writing hi = mid - 1 in the second branch. That branch runs when mid could be the minimum itself. 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, mid equals both, nums[mid] > nums[hi] is false, and hi = mid changes nothing: the loop never ends. Stop when the range has one element, with lo < hi.
Comparing with nums[lo] instead of nums[hi]. In the unrotated list [1, 2, 3, 4, 5], the middle value 3 is above nums[0] = 1, which looks like the drop is to the right, so the search moves away from the true minimum at index 0 and returns 4.
Returning lo instead of nums[lo]. The task asks for the value; the index is the answer to a different question (see the FAQ on the rotation count).
Assuming the list was rotated. A rotation by 0 is allowed, and code that hunts for a drop with no fallback reads past the end or returns nothing. Return nums[0] when no drop exists.

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. Each step keeps one half of the range, so a list of 5000 elements needs at most 13 comparisons. The scan for 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]?

Because nums[hi] always settles which side the minimum is on, and nums[lo] does not. If nums[mid] > nums[hi], the values must fall between mid and hi; otherwise nums[mid..hi] climbs and the minimum is at mid or before it. With nums[lo], the result nums[mid] > nums[lo] fits both an unrotated list, 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 return lo, the index of the minimum, instead of nums[lo]. If you count a rotation as moving the last element to the front, that index is the rotation count. If you count it as moving the first element to the back, as this problem does, the count is (n - lo) mod n: in [11, 13, 15, 17, 2, 5, 9] the minimum is at index 4, and 7 minus 4 gives the 3 values moved.

Does the binary search work when the array has duplicates?

Not unchanged. In [2, 2, 2, 0, 2], nums[mid] can equal nums[hi], and then neither side is ruled out. Shrinking with hi = hi - 1 in that case is safe, because a copy of nums[hi] stays in range at mid, but a list of equal values with one smaller value hidden among them then costs O(n).

Python

def findMin(nums):
    # Write code here

Test cases

Case 1

Case 2

Case 3

Input

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

Expected