Brute Force Solution

The most straightforward approach is to iterate through the entire array and find the minimum element. This involves comparing each element with the current minimum and updating the minimum if a smaller element is found.

Code:

def find_min_brute_force(nums):
    min_val = nums[0]
    for i in range(1, len(nums)):
        if nums[i] < min_val:
            min_val = nums[i]
    return min_val

Time Complexity

O(n), where n is the number of elements in the array, as we need to iterate through each element once.

Space Complexity

O(1), as we only use a constant amount of extra space to store the minimum value.

Optimal Solution (Binary Search)

Since the array is sorted and rotated, we can use binary search to find the minimum element in O(log n) time. The key idea is to compare the middle element with the elements at the left and right boundaries. If the middle element is greater than the rightmost element, then the minimum element must be in the right half. Otherwise, the minimum element must be in the left half (including the middle element).

Algorithm:

1. Initialize left = 0 and right = len(nums) - 1.
2. While left < right:
   • Calculate mid = left + (right - left) // 2 to prevent overflow.
   • If nums[mid] > nums[right], then left = mid + 1.
   • Else, right = mid.
3. Return nums[left] (or nums[right], as they are the same at this point).

Code:

def find_min(nums):
    left = 0
    right = len(nums) - 1

    while left < right:
        mid = left + (right - left) // 2
        if nums[mid] > nums[right]:
            left = mid + 1
        else:
            right = mid

    return nums[left]

Time Complexity

O(log n), where n is the number of elements in the array, due to the binary search approach.

Space Complexity

O(1), as we only use a constant amount of extra space.

Edge Cases

• Empty Array: The problem statement specifies that 1 <= n <= 5000, which means the array will not be empty. However, in a real-world scenario, it's good practice to handle this edge case by adding a check at the beginning of the function.
• Array with one element: If the array contains only one element, that element is the minimum.
• Array is not rotated: If the array is sorted in ascending order and not rotated, the minimum element is the first element.
• Duplicate values: The problem states that all integers of nums are unique. If duplicate values were allowed, the binary search approach would need to be modified to handle cases where nums[mid] == nums[right]. We could resolve this by simply decrementing the right pointer until nums[mid] != nums[right].

Summary

The optimal solution using binary search provides a significant improvement in time complexity compared to the brute-force approach, making it more efficient for large arrays.