153. Find Minimum in Rotated Sorted Array
Model: qwen3.5:9b
Topics: Array,Binary Search
FAANG asked: 1
Acceptance rate: 46.4%
Problem Breakdown
We are given an integer array nums that was originally sorted in ascending order but has been rotated (cyclically shifted) some number of times between 1 and n. For example, [1,2,3] becomes [3,1,2] after one rotation. We need to find the minimum element in this array.
Inputs: A list of integers nums.
Outputs: The single integer representing the minimum value.
Implicit Constraints & Edge Cases:
- Unique Elements: All elements are distinct (no duplicates). This simplifies binary search logic significantly compared to versions with duplicates.
- Length: . We don’t need to handle empty arrays, but we must ensure the code works for a single-element array () where
leftequalsright. - Range: Values are between -5000 and 5000. Standard integer types suffice; no overflow issues in Python or standard languages here.
Intuition
A naive approach would be to iterate through the entire array using a linear scan () to find the minimum value. While this works, it ignores the fact that the input is derived from a sorted sequence. We should leverage the “sorted” property for efficiency.
Since the original array was sorted and then rotated, there exists exactly one point where the order breaks (the pivot). For example: [4, 5, 6] followed by [0, 1, 2]. The minimum element is always at this drop-off or immediately after it.
Because we have a monotonic property on either side of the rotation break, we can use Binary Search to find the pivot in time instead of scanning every element.
The key insight for binary search here: We compare nums[mid] with nums[right]. Why not left? Because if the array is rotated, the left side might be part of a higher-value segment (e.g., [4...7]). However, we know that within any valid sorted subarray, values increase. If nums[mid] < nums[right], it implies that the range from mid to right is strictly increasing and contains no rotation break inside this specific window; therefore, the minimum must be on the left side (or at mid). Conversely, if nums[mid] > nums[right], we are in a rotated segment where values decrease as indices increase towards the end of that subarray, meaning the pivot/minimum is to the right.
Approach
- Initialize two pointers:
leftpointing to index 0 andrightpointing to index . - Enter a loop while
left < right. This ensures we narrow down until both point to the same element (the minimum). - Calculate
mid = left + (right - left) // 2to avoid potential overflow in other languages, though Python handles large integers automatically. - Compare
nums[mid]withnums[right]:- Case A (
nums[mid] < nums[right]): The right half[mid...right]is sorted ascendingly. Since the array was originally sorted and rotated, if we are in a sorted segment on the right side of mid, the minimum cannot be to the right ofmid. We can discard the right half by settingright = mid. - Case B (
nums[mid] > nums[right]): The subarray[left...right]is not fully sorted. Since elements are unique and originally ascending, this implies we have crossed the rotation point (the drop). The minimum value must be somewhere betweenmid + 1andright. We discard the left half by settingleft = mid + 1.
- Case A (
- When
left == right, that element is guaranteed to be the pivot/minimum because all other elements have been eliminated from consideration as candidates for being smaller than it in a sorted context relative to this search space.
Complexity Analysis
- Time Complexity: . We halve the search space with every iteration, characteristic of binary search. Even though we are searching within a rotated array, the logic remains logarithmic because at each step we eliminate half of the remaining candidates based on value comparison.
- Space Complexity: . We only use two pointers (
left,right) and do not allocate additional data structures proportional to input size.
Solution
def findMin(nums):
left, right = 0, len(nums) - 1
# Loop until the search space is reduced to a single element
while left < right:
mid = (left + right) // 2
# Compare mid with right.
# We compare with 'right' because if nums[mid] < nums[right],
# it implies the segment [mid...right] is sorted ascendingly,
# meaning the minimum must be to the left of or at mid.
if nums[mid] < nums[right]:
right = mid # Minimum could be here (at mid) or on the left side
else:
left = mid + 1 # We are in a rotated segment; min is strictly to the right
return nums[left]
# Example usage for verification
print(findMin([3,4,5,1,2])) # Output: 1
print(findMin([4,5,6,7,0,1,2])) # Output: 0
print(findMin([11,13,15,17])) # Output: 11 (Already sorted)
Edge Cases Handled
- Single Element Array (): The loop condition
left < rightis false immediately. Returnsnums[0], which is correct as it’s the only element and thus minimum. - Fully Sorted Array: If rotated times (effectively
[1,2,3]), logic treats it like a standard sorted array wheremid < rightalways holds until convergence on index 0. Wait, actually if fully sorted ascendingly: e.g.,[1,2,3].- Iteration 1: mid=1 (val 2). nums[1]=2 < nums[2]=3 -> right = 1.
- Iteration 2: left=0, right=1. mid=0 (val 1). nums[0]=1 < nums[1]=2 -> right = 0.
- Loop ends. Returns
nums[0]. Correct.
- Minimum at Start: e.g.,
[4,5,6,7,0,1,2](min is 0). Logic correctly identifies that mid > right eventually pushes left pointer past the drop point until it lands on min. - Negative Numbers: The logic relies only on relative ordering (
<,>), not absolute values, so negative numbers are handled naturally without modification.