31.Find Minimum in Rotated Sorted Array

MediumBlind 75Binary Search · 4/7

Problem

An array of unique integers sorted in ascending order has been rotated between 1 and n times. Rotating [a0, a1, ..., a(n-1)] once gives [a(n-1), a0, a1, ..., a(n-2)]. For example [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2] (rotated 4 times) or stay [0,1,2,4,5,6,7] (rotated 7 times).

Given the rotated array nums, return its minimum element in O(log n) time.

Examples

Input:  nums = [3, 4, 5, 1, 2]
Output: 1
Explanation: The original array was [1, 2, 3, 4, 5], rotated 3 times.

Input:  nums = [4, 5, 6, 7, 0, 1, 2]
Output: 0
Explanation: The original array was [0, 1, 2, 4, 5, 6, 7], rotated 4 times.

Input:  nums = [11, 13, 15, 17]
Output: 11
Explanation: Rotated 4 times (a full cycle), so the array is sorted and the minimum is the first element.

Constraints

n == nums.length
1 <= n <= 5000
-5000 <= nums[i] <= 5000
All integers in nums are unique.
nums is sorted and rotated between 1 and n times.

💡 Key Insight

A rotated sorted array is two ascending runs: a left run of large values followed by a right run of small values, and the minimum is the first element of the right run. Comparing nums[mid] with nums[right] tells us which run mid is in: if nums[mid] > nums[right], mid is in the left (large) run and the minimum is strictly to its right; otherwise mid is in the right run and the minimum is at mid or to its left.

Brute Force

TimeO(n)SpaceO(1).

Intuition

Scan the whole array and keep the smallest value seen.

Algorithm

min = nums[0].
For each value, min = Math.min(min, value).
Return min.

Visualization

nums = [3, 4, 5, 1, 2]
min: 3 → 3 → 3 → 1 → 1   → return 1

Code

java

class Solution {
    public int findMin(int[] nums) {
        int min = nums[0];
        for (int value : nums) {
            min = Math.min(min, value);
        }
        return min;
    }
}

Complexity

Time: O(n) — every element is inspected.
Space: O(1).

Binary Search with Sorted-Window Check

TimeO(log n)SpaceO(1).

Intuition

Keep a running answer res. At each step, if the window [l, r] is already sorted (nums[l] < nums[r]), its minimum is simply nums[l] and we can stop. Otherwise the rotation point is inside the window. Record nums[mid] as a candidate, then decide: if nums[mid] >= nums[l], mid belongs to the left (large) run, so search right; otherwise search left.

Algorithm

res = nums[0], l = 0, r = n - 1.
While l <= r:
- If nums[l] < nums[r]: res = min(res, nums[l]) and break.
- mid = l + (r - l) / 2, res = min(res, nums[mid]).
- If nums[mid] >= nums[l], l = mid + 1; else r = mid - 1.
Return res.

Dry Run

nums = [4, 5, 6, 7, 0, 1, 2]
l=0, r=6: not sorted, mid=3 (7), res=4; 7 ≥ 4 → l=4
l=4, r=6: nums[4]=0 < nums[6]=2 → sorted window, res=min(4,0)=0, break
return 0

Code

java

class Solution {
    public int findMin(int[] nums) {
        int res = nums[0];
        int l = 0;
        int r = nums.length - 1;
        while (l <= r) {
            if (nums[l] < nums[r]) {
                // window is fully sorted: its first element is its minimum
                res = Math.min(res, nums[l]);
                break;
            }
            int mid = l + (r - l) / 2;
            res = Math.min(res, nums[mid]);
            if (nums[mid] >= nums[l]) {
                l = mid + 1; // mid is in the left (larger) run
            } else {
                r = mid - 1; // mid is in the right (smaller) run
            }
        }
        return res;
    }
}

Complexity

Time: O(log n) — the window halves each iteration.
Space: O(1).

Binary Search Against the Right EndOptimal

TimeO(log n)SpaceO(1).

Intuition

Shrink [l, r] so that it always contains the minimum, until a single element remains. Compare with nums[r] (not nums[l]) because the right end is always in the small run, which makes the rule clean:

nums[mid] > nums[r] — mid is in the big run, minimum is in (mid, r] → l = mid + 1.
nums[mid] < nums[r] — mid is in the small run, minimum is in [l, mid] → r = mid.

Values are unique, so nums[mid] == nums[r] only when mid == r, which cannot happen while l < r.

Algorithm

l = 0, r = n - 1.
While l < r:
- mid = l + (r - l) / 2.
- If nums[mid] > nums[r], l = mid + 1; else r = mid.
Return nums[l].

Dry Run

flowchart TD
    A["nums = [4,5,6,7,0,1,2]<br/>l=0, r=6"] --> B["mid=3: 7 vs nums[r]=2"]
    B -->|"7 > 2, min is right of mid"| C["l=4, r=6"]
    C --> D["mid=5: 1 vs nums[r]=2"]
    D -->|"1 ≤ 2, min at mid or left"| E["l=4, r=5"]
    E --> F["mid=4: 0 vs nums[r]=1"]
    F -->|"0 ≤ 1"| G["l=4, r=4"]
    G --> H["l == r → return nums[4] = 0"]

Code

java

class Solution {
    public int findMin(int[] nums) {
        int l = 0;
        int r = nums.length - 1;
        while (l < r) {
            int mid = l + (r - l) / 2;
            if (nums[mid] > nums[r]) {
                l = mid + 1; // rotation point (minimum) is strictly right of mid
            } else {
                r = mid;     // mid could itself be the minimum
            }
        }
        return nums[l]; // l == r points at the minimum
    }
}

Complexity

Time: O(log n) — the window halves each iteration.
Space: O(1).

Complexity Comparison

Approach	Time	Space
Brute Force	O(n)	O(1)
Binary Search with Sorted-Window Check	O(log n)	O(1)
Binary Search Against Right End	O(log n)	O(1)

Common Pitfalls

Comparing nums[mid] with nums[l] in the l < r template — for an unrotated array like [1,2,3], nums[mid] > nums[l] would wrongly push you right. Comparing with nums[r] avoids this.
Writing r = mid - 1 when nums[mid] < nums[r] — mid itself may be the minimum and would be skipped.
Forgetting the "rotated n times" case where the array is fully sorted; both binary searches must return nums[0] there.
This logic relies on unique values. With duplicates (LeetCode 154) you need an extra r-- step when nums[mid] == nums[r].