153. Find Minimum in Rotated Sorted Array#

Difficulty: Medium

Link to Problem: To see the Find Minimum in Rotated Sorted Array problem on LeetCode, click here!

Suppose an array of length n sorted in ascending order is rotated between 1 and n times. For example, the array nums = [0,1,2,4,5,6,7] might become:

  • [4,5,6,7,0,1,2] if it was rotated 4 times.

  • [0,1,2,4,5,6,7] if it was rotated 7 times.

Notice that rotating an array [a[0], a[1], a[2], ..., a[n-1]] 1 time results in the array [a[n-1], a[0], a[1], a[2], ..., a[n-2]].

Given the sorted rotated array nums of unique elements, return the minimum element of this array.

You must write an algorithm that runs in \(O(log\ n)\) time.

Constraints:

  • n == nums.length

  • 1 <= n <= 5000

  • -5000 <= nums[i] <= 5000

  • All the integers of nums are unique.

  • nums is sorted and rotated between 1 and n times.

def findMin(nums):
    left, right = 0, len(nums) - 1
    
    while left < right:
        mid = left + (right - left) // 2
        
        # If the mid element is greater than the rightmost element,
        # it means the minimum element is in the right half.
        if nums[mid] > nums[right]:
            left = mid + 1
        # If the mid element is less than or equal to the rightmost element,
        # it means the minimum element is in the left half or at the mid itself.
        else:
            right = mid
    
    # The loop will break when left and right converge to the minimum element.
    # At this point, left (or right) will be pointing to the minimum element.
    return nums[left]

Explanation:#

  1. The function findMin(nums) takes an input list nums, which represents the rotated sorted array.

  2. Initialize two pointers left and right to track the current search range. Initially, left is set to 0 (the beginning of the array), and right is set to len(nums) - 1 (the end of the array).

  3. Enter a while loop with the condition left < right. This loop continues until left and right converge to a single element, which will be the minimum element in the rotated array.

  4. Inside the loop, calculate the middle index mid using integer division. This helps in finding the middle element of the current search range.

  5. Check if the element at the middle index (nums[mid]) is greater than the element at the rightmost index (nums[right]). If this condition is true, it means that the minimum element must be in the right half of the current search range. So, update left to mid + 1, effectively eliminating the left half of the search range.

  6. If the condition from step 5 is not met, it implies that the minimum element can be in the left half of the current search range or could be the element at the mid index itself. In this case, update right to mid, effectively eliminating the right half of the search range.

  7. Repeat steps 4-6 until left and right converge to the minimum element.

  8. When the loop exits, it means that left (or right) points to the minimum element in the array.

  9. Return nums[left] (or nums[right]) as the result, which is the minimum element in the rotated sorted array.

Test cases#

### Example 1:
nums1 = [3, 4, 5, 1, 2]
print(findMin(nums1))

1

# Example 2:
nums2 = [4, 5, 6, 7, 0, 1, 2]
print(findMin(nums2))

0

# Example 3:
nums3 = [11, 13, 15, 17]
print(findMin(nums3))

11

Let’s analyze the time and space complexity of the provided code:

Time Complexity: The time complexity of this code is \(O(log\ n)\), where ‘\(n\)’ is the length of the input array nums. This is because the binary search algorithm is employed, which continually divides the search range in half with each iteration.

In each iteration of the while loop, the search range is halved, and this process continues until the left and right pointers converge to the minimum element. In the worst case, it will take logarithmic time to reduce the search range to a single element.

Therefore, the binary search used in this code runs in \(O(log\ n)\) time complexity.

Space Complexity: The space complexity of this code is \(O(1)\), which means it uses a constant amount of additional space that does not depend on the size of the input array.

The algorithm uses a fixed number of variables (left, right, mid) to keep track of the search range and indices, but the number of these variables does not grow with the size of the input array. Hence, the space complexity is constant.

In summary:

  • Time Complexity: \(O(log\ n)\)

  • Space Complexity: \(O(1)\)

Challenging Exercises:#

  1. Solve the problem with a variation where the input array may contain duplicates.

  2. Modify the problem to return the index of the minimum element in the rotated sorted array, rather than the element itself. The algorithm should still run in \(O(log\ n)\) time.

  3. Implement a function that finds the maximum element in a rotated sorted array. How would you adapt the binary search algorithm to solve this problem efficiently in \(O(log\ n)\) time?

  4. Implement a function that can find the kth smallest element in a rotated sorted array. This is an extension of the original problem, and the algorithm should still run in \(O(log\ n)\) time.