153.Find_Minimum_in_Rotated_Sorted_Array(Medium).md

153. Find Minimum in Rotated Sorted Array (Medium)

Date and Time: Jul 19, 2024, 0:13 (EST)

Link: https://leetcode.com/problems/find-minimum-in-rotated-sorted-array/

Question:

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.

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

Notice that rotating an array [a[0], a[1], a[2], ..., a[n-1]] 1 time results in the array [a[n-1], a[0], a[1], a[2], ..., a[n-2]].

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.

KeyPoints:

In the base case, we first check if nums[l] < nums[r], if this is true that means this subarray between [l, r] is sorted, so we update res = min(res, nums[l]) (nums[l] can be the smallest).

If nums[l] !< nums[r], we find m to use binary search to see if nums[l] <= nums[m], which means we should look at [m+1: ], because the left-subarray is increasing, and the smallest element must exist in the right subarray, so we update l = m + 1.

Similarly, if nums[l] > nums[m] that means the smallest element is between [l, m], so we update r = m - 1 to look at the left-subarray only.

Base case 1: nums[l] < nums[r], this subarray is sorted, res = min(res, nums[l]).

Base case 2: if nums[l] <= nums[m]: l = m + 1. Else, r = m - 1.

My Solution:

class Solution:
    def findMin(self, nums: List[int]) -> int:
        # Base case 1: nums[l] < nums[r], this subarray is sorted, res = nums[l]
        # Base case 2: if nums[l] <= nums[m]: l = m + 1. Else, r = m - 1
        l, r = 0, len(nums)-1
        res = float("inf")
        while l <= r:
            if nums[l] < nums[r]:
                res = min(res, nums[l])
            m = (l + r) // 2
            if nums[l] <= nums[m]:
                l = m + 1
            else:
                r = m - 1
            res = min(res, nums[m])
        return res

Time Complexity: $O(log\ n)$
Space Complexity: $O(1)$