Find Minimum in Rotated Sorted Array medium

Problem Statement

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 0 times.

You must write an efficient algorithm that finds the minimum element in the rotated sorted array.

You must not use any extra space. The time complexity of your algorithm must be O(log n).

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], rotated 4 times.

Steps

The problem leverages binary search's efficiency to find the minimum element in logarithmic time. The key is understanding that the minimum element is always the only element that is smaller than its previous element (if we consider the array circularly).

1. Initialize: Set left = 0 and right = nums.length - 1.
2. Binary Search: While left < right:
   • Calculate mid = (left + right) / 2.
   • Case 1: nums[mid] > nums[right]: The minimum element lies in the right half of the array (because the right half is unsorted). Update left = mid + 1.
   • Case 2: nums[mid] <= nums[right]: The minimum element lies in the left half of the array (including nums[mid]). Update right = mid.
3. Return: After the loop, left and right will both point to the index of the minimum element. Return nums[left].

Explanation

The algorithm works because of the properties of a rotated sorted array. The rotation creates a point where the sorted order is broken. The minimum element is always to the right of this break point. By comparing nums[mid] with nums[right], we can efficiently determine which half of the array contains the minimum element and narrow down the search space in each iteration.

Code

class Solution {
    public int findMin(int[] nums) {
        int left = 0;
        int right = nums.length - 1;

        while (left < right) {
            int mid = left + (right - left) / 2; // Avoid potential overflow

            if (nums[mid] > nums[right]) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }

        return nums[left];
    }
}

Complexity

• Time Complexity: O(log n) due to the binary search.
• Space Complexity: O(1) because we use only a constant amount of extra space. The algorithm operates in-place.