Leetcode 153. Find Minimum in Rotated Sorted Array

Problem

Leetcode 153 - Find Minimum in Rotated Sorted Array

Example:

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

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.

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

Approach

Since the array is a rotated result of the sorted array, we can still use binary search to find the minimum value in the array.

Just like normal binary search we will have left and right pointer to find the mid pointer

• Note that we have to loop left < right instead of left <= right, otherwise it’ll have infinite loop

If nums[mid] > nums[right], then we know that whatever’s on the right side is smaller. Thus we have to move our left pointer.

If nums[mid] <= nums[right], then we know that from mid to right is sorted, thus we try to find from left by moving our right pointer.

Eventually once we finish the loop, we will return nums[left], because left should always keep the minimum array

Visualization of the Approach:

nums = [3,4,5,1,2]
        l       r
nums[mid] = 5
Since nums[mid] > nums[right], move left pointer

nums = [3,4,5,1,2]
              l r
nums[mid] = 1
Since nums[mid] <= nums[right], move right pointer

nums = [3,4,5,1,2]
              l
              r
Since left <= right, move get out of while loop
return left pointer since it'll always show minimum number

Thus, return 1

Here is the Python code for the solution:

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

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

            if nums[mid] > nums[right]:
                left = mid + 1
            else:
                right = mid - 1

        return nums[left]    

Time Complexity and Space Complexity

Time Complexity: $O(log n)$

Space Complexity: $O(1)$