153. Find Minimum in Rotated Sorted Array

Description

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

Note that the array is assumed to have one element.

The solution must run in O(log n) time.

Notes

This is similar to question 33. Search in Rotated Sorted Array.

O(log n) time means that binary search should be used.

Solutions

My Solution

My idea was to modify the standard binary search algorithm so that the left pointer will point at the min value in the array.

If nums[left] <= nums[right] then the array is not rotated. So we can just return nums[left]. Example, given the array [1, 2, 3, 4, 5], nums[0] < nums[4], nums[0] (value 1) is the min value of the array.

If nums[left] > nums[right] then we are in a rotated array. So, we need to determine if the mid pointer is on the left or right of the rotation point.

If the mid pointer is to the left of the rotation point, then we need to look to the right of the rotation point for the min value. For example, given the array [4, 5, 6, 7, 8, 1, 2, 3], if the mid point is at index 3 (value 7) then we know the min value must be to the right. So, set the left pointer to mid + 1.

If the mid pointer is to the right of the rotation point, then there are two scenarios to consider:

• The mid point is not on the rotation point. In this case the min value will be somewhere to the left of the mid point. For example, given the array [7, 8, 9, 10, 0, 1, 2, 3, 4, 5, 6], if mid point is at index 5 (value 1), then we are not at the rotation point, and there is still a value less than it to the left. So, set the right pointer to mid - 1.

• The mid point is on the rotation point. This is the smallest value in the array, so return it.

class Solution:
    def findMin(self, nums: List[int]) -> int:
        # short circuit for arrays with 1 element
        if len(nums) == 1:
            return nums[0]
        left = 0
        right = len(nums) - 1
        while left <= right:
            if nums[left] <= nums[right]:
                # the array isn't rotated so return the left element
                return nums[left]
            mid = (left + right) // 2
            if nums[mid] < nums[right]:
                # the mid point is on the right side of the rotation point, so items are sorted in ascending order.
                # Example: that part of the array will look like: [2, 3, 4, 5]
                if nums[mid] >= nums[mid - 1]:
                    # if the value immediately to the left of the mid is less than the mid value, then we can still find
                    # a min value to the left of the mid point. Adjust the right pointer to that place
                    right = mid - 1
                else:
                    # if the value immediately to the left of the mid point is greater than the mid point value, then
                    # we're at the rotation point. Return the mid value as it's the min value.
                    return nums[mid]
            else:
                # mid point is on the left side of the rotation point. So the min value will be somewhere to the right
                # of the mid point. Adjust the left point to that place.
                # Example: [5, 6, 7, 0, 1, 2, 3, 4]. If mid is at index 1 (value 6), then the min value is somewhere to
                # the right of mid
                left = mid + 1

Time Complexity: O(log n)

Space Complexity: O(1)

LeetCode Solution

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

class Solution(object):
    def findMin(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        # If the list has just one element then return that element.
        if len(nums) == 1:
            return nums[0]

        # left pointer
        left = 0
        # right pointer
        right = len(nums) - 1

        # if the last element is greater than the first element then there is no rotation.
        # e.g. 1 < 2 < 3 < 4 < 5 < 7. Already sorted array.
        # Hence the smallest element is first element. A[0]
        if nums[right] > nums[0]:
            return nums[0]

        # Binary search way
        while right >= left:
            # Find the mid element
            mid = left + (right - left) / 2
            # if the mid element is greater than its next element then mid+1 element is the smallest
            # This point would be the point of change. From higher to lower value.
            if nums[mid] > nums[mid + 1]:
                return nums[mid + 1]
            # if the mid element is lesser than its previous element then mid element is the smallest
            if nums[mid - 1] > nums[mid]:
                return nums[mid]

            # if the mid elements value is greater than the 0th element this means
            # the least value is still somewhere to the right as we are still dealing with elements greater than nums[0]
            if nums[mid] > nums[0]:
                left = mid + 1
            # if nums[0] is greater than the mid value then this means the smallest value is somewhere to the left
            else:
                right = mid - 1