Find Minimum in Rotated Sorted Array

Problem Statement

You are given an array of length n which was originally sorted in ascending order. It has now been rotated between 1 and n times. For example, the array nums = [1,2,3,4,5,6] might become:

  • [3,4,5,6,1,2] if it was rotated 4 times.
  • [1,2,3,4,5,6] if it was rotated 6 times.

Notice that rotating the array 4 times moves the last four elements of the array to the beginning. Rotating the array 6 times produces the original array.

Assuming all elements in the rotated sorted array nums are unique, return the minimum element of this array.

A solution that runs in O(n) time is trivial, can you write an algorithm that runs in O(log n) time?

Example 1:

Input: nums = [3,4,5,6,1,2]


Output: 1

Example 2:

Input: nums = [4,5,0,1,2,3]


Output: 0

Example 3:

Input: nums = [4,5,6,7]


Output: 4

Constraints:

  • 1 <= nums.length <= 1000
  • -1000 <= nums[i] <= 1000

You should aim for a solution with O(logn) time and O(1) space, where n is the size of the input array.

You should aim for a solution with O(log n) time and O(1) space, where n is the size of the input array.

Hint 1

A brute force solution would be to do a linear search on the array to find the minimum element. This would be an O(n) solution. Can you think of a better way? Maybe an efficient searching algorithm is helpful.

Hint 2

Given that the array is rotated after sorting, elements from the right end are moved to the left end one by one. This creates two parts of a sorted array, separated by a deflection point caused by the rotation. For example, consider the array [3, 4, 1, 2]. Here, the array is rotated twice, resulting in two sorted segments: [3, 4] and [1, 2]. And the minimum element will be the first element of the right segment. Can you do a binary search to find this cut?

Hint 3

We perform a binary search on the array with pointers l and r, which belong to two different sorted segments. For example, in [3, 4, 5, 6, 1, 2, 3], l = 0, r = 6, and mid = 3. At least two of l, mid, and r will always be in the same sorted segment. Can you find conditions to eliminate one half and continue the binary search? Perhaps analyzing all possible conditions for l, mid, and r would help.

Hint 4

There will be two conditions where l and mid will be in left sorted segment or mid and r will be in right sorted segement. If l and mid in sorted segement, then nums[l] < nums[mid] and the minimum element will be in the right part. If mid and r in sorted segment, then nums[m] < nums[r] and the minimum element will be in the left part. After the binary search we end up finding the minimum element.

Solution

Brute Force

def find_min(nums: List[int]) -> int:
    return min(nums)

Time complexity: O(n) Space complexity: O(1)

def find_min(nums: List[int]) -> int:
    res = nums[0]
    left, right = 0, len(nums) - 1


    while left <= right:
        if nums[left] < nums[right]:
            res = min(res, nums[left])
            break


        mid = (left + right) // 2
        res = min(res, nums[mid])
        if nums[mid] >= nums[left]:
            left = mid + 1
        else:
            right = mid - 1
    return res

Time complexity: O(log n) Space complexity: O(1)

Binary Search (Lower Bound)

def find_min(nums: List[int]) -> int:
    left, right = 0, len(nums) - 1
    while left < right:
        mid = left + (right - left) // 2
        if nums[mid] < nums[right]:
            right = mid
        else:
            left = mid + 1
    return nums[left]

Time complexity: O(log n) Space complexity: O(1)