LeetCode #153: Find Minimum in Rotated Sorted Array

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

Solution:

To solve this problem in Python 3, we can use a binary search algorithm to search for the minimum element in the sorted rotated array.

Here are the steps to follow:

1. Initialize two pointers, left and right, to the first and last indices of the input array nums, respectively.
2. If nums[left] < nums[right], the array is not rotated and the minimum element is nums[left]. Return nums[left].
3. Perform binary search until the left pointer is equal to the right pointer.
4. Calculate the mid index as the average of left and right.
5. If nums[mid] > nums[mid + 1], then nums[mid + 1] is the minimum element. Return nums[mid + 1].
6. If nums[mid - 1] > nums[mid], then nums[mid] is the minimum element. Return nums[mid].
7. If nums[mid] > nums[left], the minimum element is to the right of mid. Set left to mid + 1.
8. Otherwise, the minimum element is to the left of mid. Set right to mid - 1.

Here’s the Python 3 code that implements this approach:

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

In this code, we first initialize two pointers, left and right, to the first and last indices of the input array nums, respectively. We then check if nums[left] < nums[right]. If this is true, the array is not rotated and the minimum element is nums[left]. We return nums[left].

We then perform binary search by calculating the mid index and checking the values of nums[mid], nums[mid - 1], and nums[mid + 1]. If any of these conditions are met, we return the minimum element.

If none of these conditions are met, we check if the minimum element is to the right or left of mid by comparing nums[mid] to nums[left]. If nums[mid] > nums[left], the minimum element is to the right of mid, so we set left to mid + 1. Otherwise, the minimum element is to the left of mid, so we set right to mid - 1. Finally, we return the value of nums[left].

Time and Space Complexity

The time complexity of the solution is O(log n) because it uses binary search to find the minimum element. In the worst case, the algorithm needs to search through half of the input array on each iteration, resulting in O(log n) time complexity.

The space complexity of the solution is O(1) because it only uses a constant amount of extra space to store the pointers left and right and the mid index. Thus, the space used does not depend on the size of the input array.