{x}
blog image

Find Minimum in Rotated Sorted Array

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.

 

Example 1:

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

Example 2:

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.

Example 3:

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

 

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.

Solution Explanation for Finding Minimum in Rotated Sorted Array

This problem asks to find the minimum element in a rotated sorted array containing unique elements. The array is initially sorted in ascending order but has been rotated an unknown number of times. A rotated array is simply a sorted array where a prefix has been moved to the end. For example, [0,1,2,3,4,5,6] rotated twice becomes [5,6,0,1,2,3,4].

The key insight is that we can leverage binary search to achieve a time complexity of O(log n). A naive approach would involve iterating through the entire array, resulting in O(n) time complexity.

Algorithm:

The core idea is to use binary search to efficiently locate the pivot point where the rotation occurred. The minimum element will always be located immediately after this point.

  1. Base Case: If the first element is less than or equal to the last element, the array is not rotated, and the minimum is the first element.

  2. Binary Search: Otherwise, we perform a binary search:

    • Calculate the middle index mid.
    • Compare nums[0] (the first element) with nums[mid]:
      • If nums[0] <= nums[mid], the minimum element is in the right half of the array (mid + 1 to right). The left half is still sorted.
      • If nums[0] > nums[mid], the minimum element is in the left half of the array (left to mid). The right half is still sorted.
    • Repeat the process by adjusting the left and right pointers until left and right converge. At this point, nums[left] will be the minimum element.

Time Complexity Analysis:

The algorithm uses binary search, which has a time complexity of O(log n), where n is the length of the array.

Space Complexity Analysis:

The algorithm uses constant extra space, so the space complexity is O(1).

Code Examples (Python):

class Solution:
    def findMin(self, nums: List[int]) -> int:
        if nums[0] <= nums[-1]:  # Base case: array not rotated
            return nums[0]
 
        left, right = 0, len(nums) - 1
        while left < right:
            mid = (left + right) // 2  # Integer division
            if nums[0] <= nums[mid]:  # Minimum in right half
                left = mid + 1
            else:                     # Minimum in left half
                right = mid
        return nums[left] # Left and right converge at the minimum

The other code examples in Java, C++, Go, TypeScript, Rust, and JavaScript follow the same logic, differing only in syntax. They all achieve the O(log n) time complexity and O(1) space complexity.