What is the time complexity of the optimal solution to Find Minimum in Rotated Sorted Array?

The optimal solution runs in O(log n). Linear scan is O(n) time and O(1) space, simple but ignores the sorted structure.

What pattern does Find Minimum in Rotated Sorted Array use?

Find Minimum in Rotated Sorted Array uses the binary-search pattern.

What companies ask Find Minimum in Rotated Sorted Array?

Companies known to ask Find Minimum in Rotated Sorted Array: Amazon, Microsoft, Facebook, Bloomberg, Google.

What are the edge cases in Find Minimum in Rotated Sorted Array?

Watch for these edge cases: Array not rotated (rotated n times); Single element array; Two element array; Minimum at the very end of the array; All negative numbers.

How would you explain Find Minimum in Rotated Sorted Array in an interview?

Start by clarifying the uniqueness constraint—this problem has a harder variant (LC 154) with duplicates that requires different handling

What's the difference between the brute-force and optimal approach for Find Minimum in Rotated Sorted Array?

Linear scan is O(n) time and O(1) space, simple but ignores the sorted structure. Binary search achieves O(log n) time with O(1) space by exploiting the rotation property—each comparison eliminates half the search space. For small arrays (n < 10), linear scan may be faster due to lower overhead, but binary search scales dramatically better. The binary search approach requires careful handling of the comparison (mid vs right, not left) and boundary updates (right = mid, not mid - 1).

Problem Solution

Find Minimum in Rotated Sorted Array

Medium ArrayBinary Search

Key Insight:In a rotated sorted array, comparing the middle element to the rightmost element reveals which half contains the rotation point—if mid > right, the minimum must be in the right half; otherwise, it's in the left half (including mid).

Approaches

Insight Challenge

If nums[mid] > nums[right], where must the minimum be?

Narrow down candidates by eliminating impossible regions

A rotated sorted array has a special property: it consists of two sorted subarrays. The minimum element is at the boundary between them (the rotation point). By comparing the middle element with a reference point, we can determine which half contains the rotation point and eliminate the other half. This allows us to reduce the search space by half each iteration.

Algorithm

Define the search boundaries at array start and end
While multiple candidates remain:
Examine the middle element
If middle is greater than rightmost, the break point is in the right half
Otherwise, the break point is in the left half (including middle)
Return the element at the converged position

nums

Solution

Time O(log n) Space O(1)

def find_min(nums):
    left, right = 0, len(nums) - 1
    while left < right:
        mid = (left + right) // 2
        if nums[mid] > nums[right]:
            left = mid + 1
        else:
            right = mid
    return nums[left]