DSA Finding the Minimum in a Rotated Array

The problem

Find the Minimum in a Rotated Sorted Array locates the smallest value in a sorted list that was cut at one point and swapped in two parts. The list holds at least one value, and the values are distinct.

The answer is the minimum value itself. An unrotated list is allowed. Its minimum is simply its first value.

cases = [
    ([4, 5, 6, 7, 0, 1, 2], 0),
    ([1, 2, 3, 4, 5], 1),
    ([5, 1, 2, 3, 4], 1),
    ([3, 1], 1),
    ([2], 2),
]
for nums, expected in cases:
    print("nums", nums, "minimum:", expected)

Read one row at a time. The minimum of the first list is 0, and it sits right after the largest value. The last row holds one value, which is its own minimum.

Intuition: the minimum sits at the one drop

A rotated list rises, drops once, and rises again. The minimum is the first value after the drop. The first value of the whole list proves nothing, because the cut can place any value first.

The first idea scans the list and keeps the smallest value seen. It always works. Its cost is a full pass, even though the drop can be located by halving.

nums = [4, 5, 6, 1, 2, 3]
compared = 0
smallest = nums[0]
drop_at = None
for i in range(1, len(nums)):
    compared += 1
    if nums[i] < nums[i - 1]:
        drop_at = i
    smallest = min(smallest, nums[i])
print("first value:", nums[0])
print("drop at index:", drop_at, "value there:", nums[drop_at])
print("minimum:", smallest, "comparisons:", compared)

The first value is 4 and the minimum is 1. Reading the start of the list would answer wrong. The scan pays 5 comparisons for 6 values, and that price grows with the list.

Brute force: keep the smallest seen

The brute force is the scan written as a function. It holds one running minimum. Each new value replaces it only when the new value is smaller.

def find_min_brute(nums):
    smallest = nums[0]
    compared = 0
    for value in nums[1:]:
        compared += 1
        if value < smallest:
            smallest = value
    return smallest, compared

for nums in [[4, 5, 6, 1, 2, 3], [1, 2, 3, 4, 5], [2]]:
    value, compared = find_min_brute(nums)
    print("nums", nums, "minimum:", value, "comparisons:", compared)

Every list pays one comparison per extra value. A sorted list pays the same price as a rotated one. The brute force learns nothing from the rising runs inside the list.

The optimal solution: compare the middle with the right edge

Comparing the middle value with the right edge shows which side holds the drop, and the search keeps that side until one value remains. That one sentence is the whole method.

A middle value above the right edge puts the drop to the right of the middle, so the left edge moves past the middle. A middle value at or below the right edge keeps the minimum at or left of the middle, so the right edge moves to the middle itself.

def find_min(nums):
    lo = 0
    hi = len(nums) - 1
    while lo < hi:
        mid = (lo + hi) // 2
        if nums[mid] > nums[hi]:
            lo = mid + 1
        else:
            hi = mid
    return nums[lo]

cases = [
    ([4, 5, 6, 7, 0, 1, 2], 0),
    ([1, 2, 3, 4, 5], 1),
    ([5, 1, 2, 3, 4], 1),
    ([3, 1], 1),
    ([2], 2),
]
for nums, expected in cases:
    result = find_min(nums)
    print("nums", nums, "->", result, "expected:", expected, "match:", result == expected)

All five cases from the start of the article pass. The unrotated row passes with the same rule. Its middle never beats its right edge, so the right edge walks down to the first value.

Walkthrough: the minimum of the main list

The walk shrinks one range. The state is the two edges and the middle value. Each line compares the middle with the right edge and moves one edge.

nums = [4, 5, 6, 7, 0, 1, 2]
lo = 0
hi = len(nums) - 1
while lo < hi:
    mid = (lo + hi) // 2
    if nums[mid] > nums[hi]:
        print("range", lo, hi, "- mid value", nums[mid], "right edge", nums[hi], "- move: left edge past mid")
        lo = mid + 1
    else:
        print("range", lo, hi, "- mid value", nums[mid], "right edge", nums[hi], "- move: right edge to mid")
        hi = mid
print("one value left:", nums[lo], "at index", lo)

The range closes on index 4, which holds 0. That is the value right after the drop from 7. The answer is read straight off the final range.

Complexity

The scan compares each value once, so its time is O(n). The halving search cuts its range roughly in half per step, so its time is O(log n).

Both methods store only a few values at a time. Their extra space is O(1).

def find_min_steps(nums):
    lo = 0
    hi = len(nums) - 1
    steps = 0
    while lo < hi:
        mid = (lo + hi) // 2
        steps += 1
        if nums[mid] > nums[hi]:
            lo = mid + 1
        else:
            hi = mid
    return nums[lo], steps

for n in [5, 9, 17]:
    base = list(range(1, n + 1))
    cut = n // 3
    rotated = base[cut:] + base[:cut]
    value, steps = find_min_steps(rotated)
    print("values", n, "- scan comparisons:", n - 1, " halving steps:", steps, " minimum:", value)

Counts beat clocks here. At 17 values the scan pays 16 comparisons. The halving search pays 4 steps on the same rotation shape.

Edge cases and pitfalls

Moving the right edge to one before the middle is the classic bug. The middle itself can be the minimum when it sits at or below the right edge. Dropping it loses the answer, as the run below shows.

An empty list has no minimum, and the problem rules it out. Every list here holds at least one value. The single-value row needs no loop steps at all.

def find_min_buggy(nums):
    lo = 0
    hi = len(nums) - 1
    while lo < hi:
        mid = (lo + hi) // 2
        if nums[mid] > nums[hi]:
            lo = mid + 1
        else:
            hi = mid - 1
    return nums[lo]

def find_min(nums):
    lo = 0
    hi = len(nums) - 1
    while lo < hi:
        mid = (lo + hi) // 2
        if nums[mid] > nums[hi]:
            lo = mid + 1
        else:
            hi = mid
    return nums[lo]

print("buggy version on [3, 1, 2]:", find_min_buggy([3, 1, 2]))
print("correct version on [3, 1, 2]:", find_min([3, 1, 2]))
print("single value:", find_min([2]))
print("two values falling:", find_min([3, 1]))
print("two values rising:", find_min([1, 3]))
print("minimum at the last index:", find_min([2, 3, 4, 1]))
print("minimum at the first index:", find_min([1, 2, 3, 4]))

The buggy version answers 3 on a list whose minimum is 1. One wrong edge move caused the whole error. The correct version keeps the middle in range whenever the drop could sit on it.