Find Minimum in Rotated Sorted Array
Problem
Given an array nums that is sorted in ascending order and is rotated at an unknown pivot, return the minimum element in nums. You may assume no duplicate exists in the array.
- 1 ≤ nums.length ≤ 5000
- −5000 ≤ nums[i] ≤ 5000
- All integers of nums are unique
- nums is sorted and rotated between 1 and nums.length times
Example
nums = [4,5,6,7,0,1,2]0A brute-force approach would scan the entire array to find the minimum, which is inefficient for large inputs. The optimal approach uses a modified binary search to exploit the rotated sorted property. Starting with pointers at the array's ends, the algorithm compares values to determine which half contains the minimum. For example, at the first iteration, the algorithm compares nums[l]=4 and nums[r]=2. Since nums[l] > nums[r], the minimum must be in the right half. It calculates the middle index m=3, nums[m]=7, updates the result to min(4,7)=4, and moves the left pointer to m+1=4. The process repeats until the minimum is found at index 4 with value 0.
Approach
Straightforward Solution
A linear scan through the array to find the minimum element, which takes O(n) time and is inefficient for large arrays.
Core Observation
The rotated sorted array consists of two sorted subarrays. The minimum element is the only element where the previous element is greater, or it is the smallest element in the array. The key property is that if nums[l] < nums[r], the subarray is already sorted, and nums[l] is the minimum.
Path to Optimal
The key recognition signals are 'rotated sorted array' and 'find minimum' which indicate a modified binary search. The algorithm exploits the fact that one half of the array is always sorted. By comparing nums[l], nums[m], and nums[r], it determines which half contains the minimum and discards the other half, reducing the search space by half each iteration.
Optimal Approach
Use a binary search with pointers l and r. If nums[l] < nums[r], the subarray is sorted and nums[l] is the minimum. Otherwise, calculate mid m, update the result with nums[m], and decide which half to search next based on the comparison between nums[m] and nums[l]. This approach guarantees O(log n) time complexity.
Time
O(log n)
Each iteration halves the search space by discarding one half of the array based on comparisons, leading to logarithmic time complexity.
Space
O(1)
Only a fixed number of variables (pointers and result) are used, requiring constant auxiliary space.
Pattern Spotlight
Modified Binary Search (Rotated Sorted Array)
When searching in a rotated sorted array, use the property that one half is always sorted to discard half the search space by comparing boundary and middle elements, enabling O(log n) search for the minimum.
Solution
| 1 | class Solution:
|
| 2 | def findMin(self, nums: list[int]) -> int:
|
| 3 | res = nums[0]
|
| 4 | l, r = 0, len(nums) - 1
|
| 5 |
|
| 6 | while l <= r:
|
| 7 | if nums[l] < nums[r]:
|
| 8 | res = min(res, nums[l])
|
| 9 | break
|
| 10 |
|
| 11 | m = (l + r) // 2
|
| 12 | res = min(res, nums[m])
|
| 13 | if nums[m] >= nums[l]:
|
| 14 | l = m + 1
|
| 15 | else:
|
| 16 | r = m - 1
|
| 17 |
|
| 18 | return res |
| 1 | class Solution { |
| 2 | public int findMin(int[] nums) { |
| 3 | int res = nums[0]; |
| 4 | int l = 0; |
| 5 | int r = nums.length - 1; |
| 6 | |
| 7 | while (l <= r) { |
| 8 | if (nums[l] < nums[r]) { |
| 9 | res = Math.min(res, nums[l]); |
| 10 | break; |
| 11 | } |
| 12 | |
| 13 | int m = l + (r - l) / 2; |
| 14 | res = Math.min(res, nums[m]); |
| 15 | if (nums[m] >= nums[l]) { |
| 16 | l = m + 1; |
| 17 | } else { |
| 18 | r = m - 1; |
| 19 | } |
| 20 | } |
| 21 | |
| 22 | return res; |
| 23 | } |
| 24 | } |
Step-by-Step Solution
Initialize Result and Search Boundaries
| 3 | res = nums[0]
|
| 4 | l, r = 0, len(nums) - 1
|
Objective
To set up the initial minimum candidate and pointers for the binary search over the rotated array.
Key Insight
Starting with res as nums[0] ensures the algorithm always has a baseline minimum to compare against. Initializing pointers l and r at the array boundaries sets the stage for a binary search that progressively narrows the search space to find the minimum element.
Interview Quick-Check
Core Logic
Initialize res with nums[0] to track the minimum found so far during the binary search.
State & Boundaries
Set l and r to the start and end indices of the array to cover the entire search space initially.
Iteratively Narrow Search Space Using Modified Binary Search
| 6 | while l <= r:
|
| 7 | if nums[l] < nums[r]:
|
| 8 | res = min(res, nums[l])
|
| 9 | break
|
| 11 | m = (l + r) // 2
|
| 12 | res = min(res, nums[m])
|
| 13 | if nums[m] >= nums[l]:
|
| 14 | l = m + 1
|
| 15 | else:
|
| 16 | r = m - 1
|
Objective
To repeatedly halve the search space by comparing boundary and middle elements, updating the minimum candidate accordingly.
Key Insight
If the subarray between l and r is sorted (nums[l] < nums[r]), the minimum is nums[l], and the search can terminate early. Otherwise, the middle element nums[m] is compared to nums[l] to determine which half contains the minimum. Updating res with nums[m] ensures the minimum is tracked even when the minimum lies at mid. Adjusting l or r based on this comparison discards the half that cannot contain the minimum, guaranteeing logarithmic time complexity.
Interview Quick-Check
Core Logic
If nums[l] < nums[r], the subarray is sorted and nums[l] is the minimum; otherwise, use nums[m] to decide which half to discard.
State & Boundaries
The loop continues while l <= r, ensuring all elements are considered.
Common Pitfalls & Bugs
Failing to update res with nums[m] can miss the minimum if it lies at mid.
Complexity
Each iteration reduces the search space by half, leading to O(log n) time complexity.
Return the Minimum Element Found
| 18 | return res |
Objective
To output the smallest element found after the binary search completes.
Key Insight
After the loop terminates, res holds the minimum element found during the search. Returning res provides the correct answer efficiently.
Interview Quick-Check
Core Logic
Return the tracked minimum value res after the search completes.
Line Analysis
This solution has 3 Critical lines interviewers watch for.
if nums[l] < nums[r]:Check if the current subarray is already sorted.
If nums[l] < nums[r], the subarray is sorted and nums[l] is the minimum, allowing early termination and optimization.
res = min(res, nums[m])Update the minimum result with the middle element.
Including nums[m] in the minimum check ensures the algorithm does not miss the minimum if it lies at mid.
if nums[m] >= nums[l]:Check if the middle element is greater than or equal to the left boundary element.
If nums[m] >= nums[l], the left half is sorted, so the minimum must be in the right half, guiding the search direction.
res = min(res, nums[l])Update the minimum result with nums[l] if the subarray is sorted.
Since the subarray is sorted, nums[l] is guaranteed to be the smallest element in this range, so updating res ensures correctness.
l = m + 1Move the left pointer to search the right half.
Discarding the left half by moving l to m + 1 focuses the search on the half that must contain the minimum.
else:Otherwise, move the right pointer to search the left half.
If nums[m] < nums[l], the minimum lies in the left half, so adjusting r to m - 1 narrows the search accordingly.
return resReturn the minimum element found after the search completes.
Returning res provides the final answer, which has been updated to the smallest element encountered during the search.
res = nums[0]Initialize the result variable with the first element of the array.
Starting with nums[0] as the initial minimum ensures the algorithm has a baseline to compare against and never returns an uninitialized value.
while l <= r:Begin the binary search loop, continuing while the search space is valid.
The condition l <= r ensures all elements within the current search boundaries are considered, preventing infinite loops and missing elements.
breakBreak out of the loop as the minimum has been found.
Early termination avoids unnecessary further search, improving efficiency without sacrificing correctness.
m = (l + r) // 2Calculate the middle index of the current search space.
Finding the midpoint divides the search space, enabling binary search to discard half the elements each iteration.
r = m - 1Update the right pointer to narrow the search space.
Adjusting r ensures the search space shrinks correctly, maintaining the binary search invariant.
l, r = 0, len(nums) - 1Set left and right pointers to the start and end of the array.
These pointers define the current search boundaries for the binary search, covering the entire array initially.
Test Your Understanding
Why does comparing nums[m] with nums[l] allow us to discard half of the search space?
Because if nums[m] >= nums[l], the left half is sorted and the minimum must be in the right half, so we can safely discard the left half by moving l to m + 1; otherwise, the minimum lies in the left half, so we move r to m - 1.
Related Problems
Binary Search pattern
Don't just read it. Drill it.
Reconstruct Find Minimum in Rotated Sorted Array from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.
Unlock the Find Minimum in Rotated Sorted Array drill