Leetcode 153 - Find Minimum in Rotated Sorted Array

Table of contents

Problem

Suppose an array of length n sorted in ascending order is rotated between 1 and n times. For example, the array nums = [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2] if it was rotated 4 times, or [0,1,2,4,5,6,7] if it was rotated 7 times.

Given the sorted rotated array nums of unique elements, return the minimum element of this array.

You must write an algorithm that runs in O(log n) time.

Example 1:

Input: nums = [3,4,5,1,2]
Output: 1
Explanation: The original array was [1,2,3,4,5] rotated 3 times.

Example 2:

Input: nums = [4,5,6,7,0,1,2]
Output: 0
Explanation: The original array was [0,1,2,4,5,6,7] and it was rotated 4 times.

Example 3:

Input: nums = [11,13,15,17]
Output: 11
Explanation: The original array was [11,13,15,17] and it was rotated 4 times.

Constraints:

• n == nums.length
• 1 <= n <= 5000
• -5000 <= nums[i] <= 5000
• All the integers of nums are unique.
• nums is sorted and rotated between 1 and n times.

Explanation/Approach

The problem is to find the minimum element in a rotated sorted array. The key to an O(log n) solution is using binary search, which efficiently narrows down the part of the array that contains the minimum element.

• Binary Search: The approach involves comparing the middle element of the array with the endpoints and reducing the search space based on the sorted properties of the array.

Solution: Binary Search

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

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

            if nums[mid] > nums[right]:
                # Minimum is in the right part
                left = mid + 1
            else:
                # Minimum is in the left part or at mid
                right = mid

        return nums[left]

Time and Memory Complexity

The time complexity is O(log n), as binary search cuts the search space in half with each iteration. The space complexity is O(1) as it uses constant space.

Explanation

This solution uses binary search to find the minimum element. If the middle element is greater than the rightmost element, the minimum element must be to the right of the middle element. Otherwise, it is to the left, including possibly the middle element itself. The search space is reduced in each step until the minimum element is found.

Visualization

Initial Array: [4, 5, 6, 7, 0, 1, 2]
Target: 0

Iteration 1:
    left = 0, right = 6, mid = 3 (value 7)
    Array: [4, 5, 6, 7, 0, 1, 2]
                     ↑
    Search in the right half (because target < 7)

Iteration 2:
    left = 4, right = 6, mid = 5 (value 1)
    Array:       [0, 1, 2]
                     ↑
    Search in the left half (because target < 1)

Iteration 3:
    left = 4, right = 4, mid = 4 (value 0)
    Array:       [0]
                  ↑
    Found target at index 4