Problem Statement

You have an array of length n, which was initially sorted in ascending order. This array was then rotated x times. It is given that 1 <= x <= n. For example, if you rotate [1, 2, 3, 4] array 3 times, resultant array is [2, 3, 4, 1].

Your task is to find the minimum element from this array. Note that the array contains unique elements.

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

Example 1:

• Input: [8, 1, 3, 4, 5]
• Expected Output: 1
• Justification: The smallest number in the array is 1.

Example 2:

• Input: [4, 5, 7, 8, 0, 2, 3]
• Expected Output: 0
• Justification: The smallest number in the array is 0.

Example 3:

• Input: [7, 9, 12, 3, 4, 5]
• Expected Output: 3
• Justification: In this rotated array, the smallest number present is 3.

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

To determine the minimum element in a rotated sorted array, we'll leverage the binary search method.

In a standard sorted array, the elements increase (or remain the same) from left to right. But in our rotated sorted array, at some point, there will be a sudden drop, which indicates the start of the original sorted sequence and, hence, the minimum element. This drop will be our guide during the search. With binary search, we'll repeatedly halve our search range until we pinpoint the location of this sudden drop or the smallest element.

1. Initialization: Start with two pointers, left and right, set at the beginning and the end of the array, respectively.

2. Binary Search Process:

   • Calculate the middle index, mid.
   • If the element at mid is greater than the element at right, this indicates that the minimum element is somewhere to the right of mid. Hence, update left to mid + 1.
   • Otherwise, the minimum element is to the left, so update right to mid.

3. Termination: The loop will eventually lead left to point to the minimum element. This happens when left equals right.

4. Edge Case Handling: If the array isn't rotated at all, the smallest element will be the first. Our binary search process accounts for this scenario.

Algorithm Walkthrough

Let's trace the second example, [4, 5, 7, 8, 0, 2, 3]. Move through the steps one at a time:

Code

Complexity Analysis

Time Complexity: O(log n) because we are using a binary search approach, which reduces the problem size by half in each step.

Space Complexity: O(1) as we are using a constant amount of space regardless of the input size.