LeetCode #153 Find Minimum in Rotated Sorted Array

Posted on | Post modified | In , , , , , ,

Problem

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.

Examples

Example 1:

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

Example 2:

1
2
Input: [4,5,6,7,0,1,2]
Output: 0

Solution

Method: Divide and Conquer

Time Complexity: O(n log n)

Space Complexity: O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution:
    def findMin(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        # what should I return if nums is an empty list
        low = 0
        high = len(nums)
        
        while low < high:
            if nums[low] < nums[high - 1]:
                return nums[low]
            else:
                mid = (low + high)//2

                if mid == high - 1:
                    return min(nums[low], nums[high - 1])
                elif nums[mid] < nums[mid - 1] and nums[mid] < nums[mid + 1]:
                    return nums[mid]
                else:
                    left = nums[low:mid]
                    right = nums[mid:high]
                    if left[0] > left[-1]:
                        high = mid
                    if right[0] > right[-1]:
                        low = mid

or

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def findMin(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        low = 0
        high = len(nums) - 1
        
        while low < high:
            mid = (low + high) // 2
            if nums[mid] > nums[high]:
                low = mid + 1
            else:
                high = mid
                
        return nums[low]