What is the brute force approach and complexity for Find Minimum in Rotated Sorted Array?

Walk the whole array and keep the smallest value with time complexity O(N) and space complexity O(1).

What is the optimal approach and complexity for Find Minimum in Rotated Sorted Array?

Compare nums[mid] with nums[hi]: bigger → go right, else keep mid and go left with optimal time complexity O(log N) and space complexity O(1).

How do you identify the pattern for Find Minimum in Rotated Sorted Array?

Look for key signals in the prompt: "sorted array, then rotated" indicates Not fully sorted, but made of two sorted runs. Binary search still works if one check tells you which run mid is in.; "find the minimum" indicates There is no target. You are looking for a position — the drop — not a value.; "O(log n)" indicates A linear scan is ruled out. Halve the range each step.; "distinct values" indicates `nums[mid] == nums[hi]` only happens when mid == hi, so the two-way check is always clear..

Find Minimum in Rotated Sorted Array

Medium·LeetCode #153Basic Anchor

LeetCode

Jump:

30-Second Mental ModelBinary Search (rotated array — find the pivot)

Complexity:O(N)→O(log N)

Key Insight

The array is a high run followed by a low run, and the minimum is where the low run starts (the "drop"). Compare nums[mid] with nums[hi]. If nums[mid] > nums[hi], mid is in the high run, so the drop is to the right: lo = mid + 1. Otherwise mid is already in the low run (or the array is sorted), so the minimum is at mid or to its left: hi = mid. Each step halves the range.

Core Validity Invariant

Within [lo, hi], nums[mid] > nums[hi] is true exactly when mid is before the drop. So the minimum is right of mid when it is true, and at mid or left of it when it is false.

Problem

Someone took a sorted array of distinct numbers (smallest to largest) and rotated it: they cut it at some point and moved the front part to the back. For example, [0, 1, 2, 4, 5, 6, 7] can become [4, 5, 6, 7, 0, 1, 2]. They may also have rotated it by 0 steps, so it can still be fully sorted.

You get the rotated array nums. Return its smallest element. Your solution must run in O(log n) time.

Input

An integer array nums: a sorted array of distinct values, rotated 0 to n − 1 times.

Output

The minimum value in nums.

Example 1

Input: nums = [3, 4, 5, 1, 2]

Output: 1

The original array was [1, 2, 3, 4, 5], rotated 3 times. The values climb 3, 4, 5, then drop to 1. The value right after the drop is the minimum.

Example 2

Input: nums = [4, 5, 6, 7, 0, 1, 2]

Output: 0

The drop is from 7 to 0, so 0 is the minimum.

Example 3

Input: nums = [11, 13, 15, 17]

Output: 11

Rotated 4 times (a full circle), so it is still sorted. There is no drop, and the minimum is the first element.

Constraints

• 1 ≤ n ≤ 5000
• −5000 ≤ nums[i] ≤ 5000
• All values are distinct.
• nums is a sorted array rotated between 1 and n times (rotating n times gives back the sorted array).

First, think yourself

Before opening any solution, try to answer these on paper. Use hints only when stuck — each hint is counted.

1.
If you draw the values as a line graph, what shape does a rotated sorted array make?
2.
Where exactly is the minimum in that shape?
3.
If I pick a middle element, can I tell whether it is in the 'high' part or the 'low' part of the array?
4.
Which element should I compare nums[mid] with to answer that — and does it still work if the array was not rotated at all?
5.
Could mid itself be the minimum? What does that mean for how I move hi?

Brute force approach

Idea

Forget the rotation. Look at every element and keep the smallest one seen so far.

Thinking process

1
The minimum is one of the elements, so checking all of them is guaranteed to find it.
2
One loop, one variable best.
3
This ignores the fact that the array is almost sorted, so it can't be O(log n).

Code & Implementation

brute.cpp

class Solution {
public:
    int findMin(vector<int>& nums) {
        // Look at every element and keep the smallest.
        int best = nums[0];
        for (int x : nums) {
            best = min(best, x);
        }
        return best;
    }
};

class Solution {
    public int findMin(int[] nums) {
        // Look at every element and keep the smallest.
        int best = nums[0];
        for (int x : nums) {
            best = Math.min(best, x);
        }
        return best;
    }
}

class Solution:
    def findMin(self, nums: list[int]) -> int:
        # Look at every element and keep the smallest.
        best = nums[0]
        for x in nums:
            best = min(best, x)
        return best

export function findMin(nums: number[]): number {
    // Look at every element and keep the smallest.
    let best = nums[0];
    for (const x of nums) {
        best = Math.min(best, x);
    }
    return best;
}

Complexity

Time O(N)Space O(1)

Correct and simple, but the problem asks for O(log n). A linear scan learns nothing from the sorted structure.

Optimized approach

Idea

Start from brute force

Brute force checks every element, as if the array were random. But it isn't random: it is two sorted runs, and the minimum sits at the one place where the values go down.

Find the repeated work

Inside a sorted run, the values only go up, so most of them can never be the minimum. Brute force still looks at all of them. One comparison at mid can tell us which whole half the drop is in, so we can skip the other half without looking at it.

Define the state — what variables do I need?

lo, hi: The minimum is always somewhere in nums[lo … hi]. Everything outside has been proven not to be the minimum.
mid: The middle of the current range. We compare nums[mid] with nums[hi] to learn which side of the drop mid is on.

Define validity

Within [lo, hi], nums[mid] > nums[hi] is true exactly when mid is before the drop. So the minimum is right of mid when it is true, and at mid or left of it when it is false.

Define the transitions — when does each pointer move, and why is it safe?

nums[mid] > nums[hi]

lo = mid + 1

Going from mid to hi, the value went down somewhere. In a rotated sorted array that only happens at the drop, so the drop (the minimum) is in mid+1 … hi. And mid is bigger than nums[hi], so mid is not the minimum.

nums[mid] < nums[hi]

hi = mid

Values from mid to hi only go up, so nothing in mid+1 … hi is smaller than nums[mid]. The minimum is mid or something left of it. We keep mid because it might be the answer.

lo == hi

return nums[lo]

Only one candidate is left, and we never threw away the minimum.

What does the current window add to the answer?

Each comparison removes about half of the remaining range, and the removed half is proven not to contain the minimum.

Code & Implementation

optimal.cpp

class Solution {
public:
    int findMin(vector<int>& nums) {
        int lo = 0, hi = (int)nums.size() - 1;

        // Loop style: while (lo < hi) with hi = mid.
        // The minimum is always inside [lo, hi]; we stop when one element is left.
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            if (nums[mid] > nums[hi]) {
                // mid is in the left (bigger) part, so the drop is to the right of mid.
                // nums[mid] is bigger than nums[hi], so mid itself can't be the minimum.
                lo = mid + 1;
            } else {
                // nums[mid] < nums[hi]: mid..hi is sorted, so nothing after mid is smaller.
                // mid itself might be the minimum, so keep it.
                hi = mid;
            }
        }
        return nums[lo];
    }
};

class Solution {
    public int findMin(int[] nums) {
        int lo = 0, hi = nums.length - 1;

        // Loop style: while (lo < hi) with hi = mid.
        // The minimum is always inside [lo, hi]; we stop when one element is left.
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            if (nums[mid] > nums[hi]) {
                // mid is in the left (bigger) part, so the drop is to the right of mid.
                // nums[mid] is bigger than nums[hi], so mid itself can't be the minimum.
                lo = mid + 1;
            } else {
                // nums[mid] < nums[hi]: mid..hi is sorted, so nothing after mid is smaller.
                // mid itself might be the minimum, so keep it.
                hi = mid;
            }
        }
        return nums[lo];
    }
}

class Solution:
    def findMin(self, nums: list[int]) -> int:
        lo, hi = 0, len(nums) - 1

        # Loop style: while (lo < hi) with hi = mid.
        # The minimum is always inside [lo, hi]; we stop when one element is left.
        while lo < hi:
            mid = lo + (hi - lo) // 2
            if nums[mid] > nums[hi]:
                # mid is in the left (bigger) part, so the drop is to the right of mid.
                # nums[mid] is bigger than nums[hi], so mid itself can't be the minimum.
                lo = mid + 1
            else:
                # nums[mid] < nums[hi]: mid..hi is sorted, so nothing after mid is smaller.
                # mid itself might be the minimum, so keep it.
                hi = mid

        return nums[lo]

export function findMin(nums: number[]): number {
    let lo = 0;
    let hi = nums.length - 1;

    // Loop style: while (lo < hi) with hi = mid.
    // The minimum is always inside [lo, hi]; we stop when one element is left.
    while (lo < hi) {
        const mid = Math.floor(lo + (hi - lo) / 2);
        if (nums[mid] > nums[hi]) {
            // mid is in the left (bigger) part, so the drop is to the right of mid.
            // nums[mid] is bigger than nums[hi], so mid itself can't be the minimum.
            lo = mid + 1;
        } else {
            // nums[mid] < nums[hi]: mid..hi is sorted, so nothing after mid is smaller.
            // mid itself might be the minimum, so keep it.
            hi = mid;
        }
    }
    return nums[lo];
}

Complexity

Time O(log N)Space O(1)

Each step throws away about half of [lo, hi], so there are about log₂(5000) ≈ 13 steps.

Why does this algorithm work?

Dry run

All approaches compared

Approach	Idea	Time	Space
Brute Force	Walk the whole array and keep the smallest value	O(N)	O(1)
Optimal	Compare nums[mid] with nums[hi]: bigger → go right, else keep mid and go left	O(log N)	O(1)

Why does this belong to this pattern?

Clues in the problem statement

“sorted array, then rotated”Not fully sorted, but made of two sorted runs. Binary search still works if one check tells you which run mid is in.
“find the minimum”There is no target. You are looking for a position — the drop — not a value.
“O(log n)”A linear scan is ruled out. Halve the range each step.
“distinct values”`nums[mid] == nums[hi]` only happens when mid == hi, so the two-way check is always clear.

Rotated sorted array+find the drop (no target)+compare mid with hi→Binary Search (rotated array — find the pivot)

This is the anchor of the rotated sub-pattern. The key idea: binary search does not need a target, it needs a yes/no question at mid that tells you which half to keep. Here the question is "is nums[mid] > nums[hi]?". Search in Rotated Sorted Array builds on this (find which half is sorted, then check the target), and Find Peak Element uses the same "which direction must the answer be in?" idea with a slope instead of a drop.

Don't make this mistake

Comparing with nums[lo] instead of nums[hi]

✗ if (nums[mid] > nums[lo]) lo = mid + 1;

✓ if (nums[mid] > nums[hi]) lo = mid + 1;

For an array that was not rotated, like [1, 2, 3, 4, 5], nums[mid] > nums[lo] is true, so you move right and lose the minimum at index 0. nums[hi] is always in the low run, so comparing with it works for every rotation, including 0.

Using hi = mid − 1

✗ else hi = mid - 1;

✓ else hi = mid;

When nums[mid] < nums[hi], mid itself might be the minimum. In [4, 5, 1, 2, 3], mid = 2 points at 1, the answer. hi = mid − 1 throws it away. This loop is while (lo < hi) with hi = mid; don't mix it with the lo <= hi / hi = mid − 1 style.

Using while (lo <= hi) with hi = mid

✗ while (lo <= hi) { ... hi = mid; }

✓ while (lo < hi) { ... hi = mid; }

When lo == hi, mid == hi and the else branch sets hi = mid again. Nothing changes, so the loop runs forever.

Pattern confusion: searching for a target

There is no target here, so there is nothing to compare nums[mid] with except the array itself. You are looking for the drop — the one place where a value is smaller than the one before it. If you catch yourself writing if (nums[mid] == target), you are solving Search in Rotated Sorted Array instead.

Want to implement this?

Write it yourself on LeetCode, then come back and compare your code with the solutions above.

Open coding workspace

How did it go?

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like Binary Search translate into production architectures and low-level memory mechanics.

LLD Real-World Story

Order Book Price Level Matching

std::lower_bound lookup in sorted price ticks for limit orders.

Explore Track

C++ Internals

CPU Branch Prediction & Cache Efficiency

Branch mispredictions in binary search and branchless mid-point arithmetic.

Explore Track

Search in Rotated Sorted Array