Find Minimum in Rotated Sorted Array - Python Leetcode

 Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.

(i.e.,  [0,1,2,4,5,6,7] might become  [4,5,6,7,0,1,2]).

Find the minimum element.

You may assume no duplicate exists in the array.

Example 1:

Input: [3,4,5,1,2] 
Output: 1

Example 2:

Input: [4,5,6,7,0,1,2]
Output: 0
class Solution:
    def findMin(self, nums: List[int]) -> int:
        if not nums:
            return 
        # If last element is greater than first element then no rotation happened
        if nums[len(nums)-1] >= nums[0]:
            return nums[0]
        
        left = 0
        right = len(nums)-1
        
        while left <= right:
            mid = int(left + (right-left)/2)
            
            # if mid > mid +1 there is a flunctuation in the increasing order
            if nums[mid] > nums[mid+1]:
                return nums[mid+1]
            
            #if mid-1 > mid there is a fluctuation happened in increasing order
            if nums[mid-1] > nums[mid]:
                return nums[mid]
            
            if nums[mid] > nums[0]:
                left = mid+1
            else:
                right = mid-1
                
        
Time Complexity : O(logn)
Space Complexity : O(1)

No comments:

Post a Comment

Featured Post

H1B Visa Stamping at US Consulate

  H1B Visa Stamping at US Consulate If you are outside of the US, you need to apply for US Visa at a US Consulate or a US Embassy and get H1...