Find Minimum in Rotated Sorted Array

Problem

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.

Examples

Example 1:

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

Example 2:

Input: nums = [4, 6, 8, 10, 0, 1, 2]
Output: 0
Explanation: The original array was [0, 1, 2, 4, 6, 8, 10] and it was rotated 4 times.

Example 3:

Input: nums = [5, 10, 15, 20]
Output: 5
Explanation: The original array was [15, 10, 15, 20] and it was rotated 4 times. 

Solution

The answer to this lies on the fact that if we can find the point on inflection and things will be simple. So if we can have 2 sub arrays A and B,

If we pick the middle element, we can compare the middle element with the leftmost (or rightmost) element. If the middle element is less than leftmost, the left half should be selected; if the middle element is greater than the leftmost (or rightmost), the right half should be selected. Using recursion or iteration, this problem can be solved in time log(n).

Video explanation

Here is the video explaining this method in detail. Please check it out:

<div class="youtube-embed"><iframe src="https://www.youtube.com/embed/mMgT8PpUFno" frameborder="0" allowfullscreen></iframe></div>

Method 1 - Naive Linear search

A naive approach is to iterate through the array linearly, comparing each element with the current minimum, and updating the minimum whenever a smaller value is found.

Complexity

• ⏰ Time complexity: O(n)
• 🧺 Space complexity: O(1)

Method 2 - Recursive Binary Search

Define a helper function, otherwise, we will need to use Arrays.copyOfRange() function, which may be expensive for large arrays.

We use a binary search approach since the rotated sorted array retains partial properties of a sorted array:

• Divide the array into two halves.
• Compare the middle element (mid) with the rightmost (right) element to determine which half to search next:
  • If a[mid] > a[right], the smallest element lies in the right half.
  • If a[mid] ≤ a[right], the smallest element lies in the left half (including mid itself).

This approach ensures that we reduce the search space logarithmically.

Key points:

1. A rotated sorted array has at least one section that is sorted.
2. The minimum element breaks the sorted sequence, making it an ideal target for binary search.
3. The key observation is to compare values at mid and right positions during each iteration.

Code

Java

class Solution {
    public int findMin(int[] nums) {
        return helper(nums, 0, nums.length - 1);
    }

    private int helper(int[] nums, int left, int right) {
        // Base case: when the search space is reduced to one element
        if (left == right) {
            return nums[left];
        }
        
        int mid = (left + right) / 2;

        // If middle element is greater than the rightmost element,
        // search in the right half
        if (nums[mid] > nums[right]) {
            return helper(nums, mid + 1, right);
        }
        
        // Otherwise, search in the left half (including mid)
        return helper(nums, left, mid);
    }
}

Python

class Solution:
    def find_min(self, nums: List[int]) -> int:
        def helper(nums: List[int], left: int, right: int) -> int:
            # Base case: when the search space is reduced to one element
            if left == right:
                return nums[left]
            
            mid = (left + right) // 2
            
            # If middle element is greater than the rightmost element,
            # search in the right half
            if nums[mid] > nums[right]:
                return helper(nums, mid + 1, right)
            
            # Otherwise, search in the left half (including mid)
            return helper(nums, left, mid)
        
        return helper(nums, 0, len(nums) - 1)

Complexity

• ⏰ Time complexity: O(log n)
• 🧺 Space complexity: O(log n)

Method 3 - Iterative Solution

Code

Java

class Solution {
    public int findMin(int[] nums) {
        int left = 0, right = nums.length - 1;
        while (left < right) {
            int mid = (left + right) / 2;  
            if (nums[mid] > nums[right]) {
                left = mid + 1;  // Minimum must be in the right half
            } else {
                right = mid;     // Minimum must be in the left half (including mid)
            }
        }
        return nums[left]; // At the end, left points to the minimum element
    }
}

Python

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  # Minimum must be in the right half
            else:
                right = mid  # Minimum must be in the left half (including mid)
        
        return nums[left]  # At the end, left points to the minimum element

Complexity

• ⏰ Time complexity: O(log n)
• 🧺 Space complexity: O(1)