Approach Summary
The minimum is in the unsorted half. Compare mid with right: if arr[mid] > arr[right], minimum is to the right.
Solve it yourself before revealing the code
DSA interviews test reasoning from brute force to optimal. Think through the constraints first.
Solution Progression (Brute Force → Most Optimized)
Understand the architectural evolution from naive baseline to optimal complexity.
| Approach | Time | Space | Core Strategy / Trade-off |
|---|---|---|---|
| 1 Approach 1: Linear Scan (Brute Force) | O(n) | O(1) | Traverse the entire array in a single pass to track the minimum value. |
| 2 Approach 2: Binary Search (Optimal) | O(log n) | O(1) | Use binary search to identify which half is sorted and narrow the search space logarithmically. |
Approach 1: Linear Scan (Brute Force)
Scan every element from left to right and track the minimum value seen. Alternatively, stop at the first element where nums[i] < nums[i - 1]. While functional, this completely ignores the sorted nature of the array and fails the required O(log n) time constraint.
Approach 1: Linear Scan (Brute Force) Implementation
Approach 1: Linear Scan (Brute Force)
class Solution {
public int findMin(int[] nums) {
int minVal = nums[0];
for (int i = 1; i < nums.length; i++) {
if (nums[i] < minVal) {
minVal = nums[i];
}
}
return minVal;
}
}class Solution {
public:
int findMin(vector<int>& nums) {
int minVal = nums[0];
for (int i = 1; i < (int)nums.size(); i++) {
if (nums[i] < minVal) {
minVal = nums[i];
}
}
return minVal;
}
};def find_min(nums: list[int]) -> int:
min_val = nums[0]
for num in nums:
if num < min_val:
min_val = num
return min_valfunction findMin(nums) {
let minVal = nums[0];
for (let i = 1; i < nums.length; i++) {
if (nums[i] < minVal) minVal = nums[i];
}
return minVal;
}Approach 2: Binary Search (Optimal)
At any midpoint mid, if nums[left] <= nums[mid], the entire left subsegment [left..mid] is sorted, meaning its minimum element is nums[left]. We record nums[left] and shift our search to the right unsorted portion (`left = mid + 1`). Otherwise, the inflection point lies in the left half: we record nums[mid] and search left (`right = mid - 1`). The loop terminates in O(log n) steps.
Approach 2: Binary Search (Optimal) Implementation
Approach 2: Binary Search (Optimal)
class Solution {
public int findMin(int[] nums) {
int n = nums.length;
int left = 0;
int right = n - 1;
int result = Integer.MAX_VALUE;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[left] <= nums[mid]) {
result = Math.min(result, nums[left]);
left = mid + 1;
} else {
result = Math.min(result, nums[mid]);
right = mid - 1;
}
}
return result;
}
}class Solution {
public:
int findMin(vector<int>& nums) {
int n = nums.size();
int left = 0;
int right = n - 1;
int result = INT_MAX;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[left] <= nums[mid]) {
result = min(result, nums[left]);
left = mid + 1;
} else {
result = min(result, nums[mid]);
right = mid - 1;
}
}
return result;
}
};def find_min(nums: list[int]) -> int:
left, right = 0, len(nums) - 1
result = float('inf')
while left <= right:
mid = left + (right - left) // 2
if nums[left] <= nums[mid]:
result = min(result, nums[left])
left = mid + 1
else:
result = min(result, nums[mid])
right = mid - 1
return int(result)function findMin(nums) {
let left = 0;
let right = nums.length - 1;
let result = Infinity;
while (left <= right) {
const mid = left + Math.floor((right - left) / 2);
if (nums[left] <= nums[mid]) {
result = Math.min(result, nums[left]);
left = mid + 1;
} else {
result = Math.min(result, nums[mid]);
right = mid - 1;
}
}
return result;
}Edge Cases to Watch
- Array rotated 0 times (already fully sorted, e.g. [11, 13, 15, 17])
- Array of length 1 or 2
- Array rotated n - 1 times (inflection point at the very start)
Master the Binary Search Pattern
Study the core invariant, step-by-step decision framework, and common interview traps for the Binary Search pattern.
How to Recognize This Pattern
- Find pivot/minimum in rotated array
Complexity Analysis
Time Complexity
O(log n)
Space Complexity
O(1)