LeetCode 153: Find Minimum in Rotated Sorted Array

Problem Restatement

We are given an array nums.

The array was originally sorted in ascending order, then rotated some number of times.

For example, this sorted array:

[0, 1, 2, 4, 5, 6, 7]

may become:

[4, 5, 6, 7, 0, 1, 2]

We need to return the minimum element.

All elements are unique, and the required time complexity is O(log n). LeetCode states the task as returning the minimum element from a rotated sorted array of unique elements.

Input and Output

Example function shape:

def findMin(nums: list[int]) -> int:
    ...

Examples

Example 1:

nums = [3, 4, 5, 1, 2]

The minimum value is:

1

Example 2:

nums = [4, 5, 6, 7, 0, 1, 2]

The minimum value is:

0

Example 3:

nums = [11, 13, 15, 17]

The array is still sorted normally.

The minimum value is:

11

First Thought: Linear Scan

The simplest solution is to scan the whole array and keep the smallest value.

class Solution:
    def findMin(self, nums: list[int]) -> int:
        best = nums[0]

        for num in nums:
            best = min(best, num)

        return best

This is correct, but it takes O(n) time.

The problem requires O(log n), so we need binary search.

Key Insight

A rotated sorted array has two sorted parts.

For example:

[4, 5, 6, 7, 0, 1, 2]

The first sorted part is:

[4, 5, 6, 7]

The second sorted part is:

[0, 1, 2]

The minimum element is the first element of the second sorted part.

We can find it by comparing nums[mid] with the rightmost value nums[right].

If:

nums[mid] > nums[right]

then mid is in the left sorted part, so the minimum must be to the right.

Otherwise:

nums[mid] <= nums[right]

then mid is in the right sorted part, so the minimum is at mid or to the left.

Algorithm

Use two pointers:

left = 0
right = len(nums) - 1

While left < right:

1. Compute the middle index.
2. Compare nums[mid] with nums[right].
3. If nums[mid] > nums[right], move left to mid + 1.
4. Otherwise, move right to mid.

When the loop ends, left == right.

That index points to the minimum element.

Walkthrough

Use:

nums = [4, 5, 6, 7, 0, 1, 2]

Start:

left = 0
right = 6

Middle:

mid = 3
nums[mid] = 7
nums[right] = 2

Since 7 > 2, the minimum is to the right.

Move:

left = mid + 1 = 4

Now:

left = 4
right = 6

Middle:

mid = 5
nums[mid] = 1
nums[right] = 2

Since 1 <= 2, the minimum is at mid or to the left.

Move:

right = mid = 5

Now:

left = 4
right = 5

Middle:

mid = 4
nums[mid] = 0
nums[right] = 1

Since 0 <= 1, move:

right = mid = 4

Now:

left = 4
right = 4

Return:

nums[left] = 0

Correctness

At every step, the minimum element remains inside the search range [left, right].

If nums[mid] > nums[right], then nums[mid] belongs to the larger left part of the rotated array. Since nums[right] is smaller than nums[mid], the rotation point must be after mid. Therefore, the minimum cannot be at mid or to its left, so moving left to mid + 1 keeps the minimum in the search range.

If nums[mid] <= nums[right], then the section from mid to right is sorted. The smallest value in that section is nums[mid]. Therefore, the minimum may be at mid, or it may be further left. Moving right to mid keeps both possibilities.

The loop stops when left == right. Since the minimum was never removed from the search range, that single remaining index must contain the minimum element.

Complexity

Implementation

class Solution:
    def findMin(self, nums: list[int]) -> int:
        left = 0
        right = len(nums) - 1

        while left < right:
            mid = (left + right) // 2

            if nums[mid] > nums[right]:
                left = mid + 1
            else:
                right = mid

        return nums[left]

Code Explanation

We begin with the whole array as the search range:

left = 0
right = len(nums) - 1

The loop continues while more than one candidate remains:

while left < right:

We compute the middle index:

mid = (left + right) // 2

If the middle value is greater than the rightmost value:

if nums[mid] > nums[right]:
    left = mid + 1

then the minimum is strictly to the right of mid.

Otherwise:

else:
    right = mid

the minimum may be at mid, so we keep mid in the range.

Finally:

return nums[left]

returns the only remaining candidate.

Testing

def run_tests():
    sol = Solution()

    assert sol.findMin([3, 4, 5, 1, 2]) == 1
    assert sol.findMin([4, 5, 6, 7, 0, 1, 2]) == 0
    assert sol.findMin([11, 13, 15, 17]) == 11
    assert sol.findMin([1]) == 1
    assert sol.findMin([2, 1]) == 1
    assert sol.findMin([5, 1, 2, 3, 4]) == 1
    assert sol.findMin([2, 3, 4, 5, 1]) == 1

    print("all tests passed")

run_tests()