Find Minimum in Rotated Sorted Array — Binary Search O(log n) Deep Dive [Google, Microsoft, Amazon]

Problem Statement#

Suppose an array of length n sorted in ascending order is rotated between 1 and n times. Given the sorted rotated array nums of unique elements, return the minimum element of this array. You must write an algorithm that runs in O(log n) time.

Example 1:

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

Example 2:

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

Example 3:

Input:  nums = [11, 13, 15, 17]
Output: 11
Reason: No rotation occurred (or rotated n times) — array is fully sorted.

Constraints:

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

Why This Problem Matters#

LeetCode 153 appears on Blind 75, NeetCode 150, and nearly every FAANG interview prep list that has a binary search section. It is frequently asked at Google, Microsoft, and Amazon — both as a standalone warm-up and as a prerequisite concept for harder follow-ups.

But the real reason this problem matters is not the code. The code is six lines. What matters is the conceptual leap it demands: recognizing that binary search does not require a fully sorted array. It only requires that, at every step, you can eliminate half the search space with certainty. A rotated sorted array gives you exactly that ability — but you have to understand why before you can exploit it.

This problem is also the gateway to a cluster of harder interview problems:

• LeetCode 154 — same problem but with duplicates. The duplicate case breaks the simple comparison and forces you to handle nums[mid] == nums[right] carefully, degrading worst-case to O(n).
• LeetCode 33 — Search in Rotated Sorted Array. Instead of finding the minimum, you search for a target. You solve it by first locating the rotation point (the minimum), then deciding which sorted half to binary-search.
• LeetCode 81 — Search in Rotated Sorted Array II (with duplicates). The hardest variant.
• LeetCode 852 — Peak Index in Mountain Array. A direct structural cousin: find the "inflection point" in an array that rises then falls.

Master LC 153 and the rest of these fall into place naturally.

Interview frequency: This problem or a variant appears in roughly 1 in 6 binary-search-heavy interviews. Microsoft and Google in particular use it as a calibration question: if a candidate reaches for linear scan, they get a nudge toward log n; if they code binary search cleanly and explain the invariant, the interviewer moves on to a harder follow-up immediately.

The Binary Search on Rotation Insight#

This is the core idea. Read it slowly — it is the only thing you need to understand.

What does a rotated sorted array look like?#

A sorted array [1, 2, 3, 4, 5, 6, 7] rotated by 4 positions becomes [4, 5, 6, 7, 1, 2, 3]. If you draw it:

Index:   0  1  2  3  4  5  6
Value:   4  5  6  7  1  2  3
                   ^
                   minimum (the "pivot point")

There are exactly two sorted segments: a "left segment" [4, 5, 6, 7] and a "right segment" [1, 2, 3]. The minimum always lives at the start of the right segment — the point where the array "dips down" from a high value to a low one.

If no rotation occurred (or the array was rotated exactly n times), the whole array is one sorted segment and the minimum is at index 0.

The key binary search invariant#

At any point during the search, your window is [left, right]. Pick mid = (left + right) // 2. Now compare nums[mid] with nums[right].

Case 1: nums[mid] > nums[right]

The mid value is greater than the rightmost value. This means the "dip" — the rotation point — must be somewhere to the right of mid. The left part of our window (from left to mid inclusive) is entirely in the elevated left segment, so the minimum cannot be there. We move: left = mid + 1.

Example window: [5, 6, 7, | 1, 2, 3]
                    ^mid        ^right
nums[mid]=7 > nums[right]=3 → dip is to the right of mid

Case 2: nums[mid] <= nums[right]

The mid value is less than or equal to the rightmost value. This means mid itself could be the minimum, or the minimum is somewhere to the left of mid. Either way, we can safely eliminate everything to the right of mid (but not mid itself). We move: right = mid.

Example window: [1, 2, 3, | 4, 5]
                 ^mid          ^right
nums[mid]=1 <= nums[right]=5 → min is at mid or left of mid

Why right = mid and not right = mid - 1? Because mid is still a candidate for the minimum. We never discard a candidate that could be the answer.

Why not compare with nums[left]?#

A common alternative is comparing nums[mid] with nums[left]. This works but is subtler — you must handle the edge case where left == mid (single-element window) carefully to avoid an infinite loop. Comparing with nums[right] is cleaner: the termination condition left < right naturally handles everything, and when the loop exits, left == right pointing at the minimum.

The non-rotated edge case#

If nums[0] < nums[n-1], the array is not actually rotated (or was rotated n times back to the original). The algorithm handles this automatically — nums[mid] will always be <= nums[right], so right keeps shrinking toward left = 0, correctly returning nums[0].

Visual Dry Run#

Let us trace through nums = [4, 5, 6, 7, 0, 1, 2] step by step.

Index:   0  1  2  3  4  5  6
Value:   4  5  6  7  0  1  2

Initial state: left = 0, right = 6

Step 1:

left=0, right=6
mid = (0+6)//2 = 3
nums[mid] = nums[3] = 7
nums[right] = nums[6] = 2
 
7 > 2  →  nums[mid] > nums[right]
         The dip is to the RIGHT of mid.
         Move left = mid + 1 = 4

Window narrows to indices [4, 5, 6] → values [0, 1, 2].

Step 2:

left=4, right=6
mid = (4+6)//2 = 5
nums[mid] = nums[5] = 1
nums[right] = nums[6] = 2
 
1 <= 2  →  nums[mid] <= nums[right]
          The min is at mid or to the LEFT of mid.
          Move right = mid = 5

Window narrows to indices [4, 5] → values [0, 1].

Step 3:

left=4, right=5
mid = (4+5)//2 = 4
nums[mid] = nums[4] = 0
nums[right] = nums[5] = 1
 
0 <= 1  →  nums[mid] <= nums[right]
          The min is at mid or to the LEFT of mid.
          Move right = mid = 4

Window narrows to index [4] → value [0].

Termination: left == right == 4. Loop exits. Return nums[4] = 0. Correct.

Trace for a non-rotated array nums = [1, 2, 3, 4, 5]:

Step 1: left=0, right=4, mid=2, nums[2]=3, nums[4]=5
        3 <= 5  →  right = 2
 
Step 2: left=0, right=2, mid=1, nums[1]=2, nums[2]=3
        2 <= 3  →  right = 1
 
Step 3: left=0, right=1, mid=0, nums[0]=1, nums[1]=2
        1 <= 2  →  right = 0
 
Termination: left=0=right. Return nums[0] = 1. Correct.

In every non-rotated case, right always shrinks leftward until it lands on index 0.

Common Mistakes#

Mistake 1: Using right = mid - 1 instead of right = mid#

# WRONG
if nums[mid] <= nums[right]:
    right = mid - 1   # BUG: discards mid, which could be the minimum

If mid is exactly the minimum, this code skips past it. The correct move is right = mid — we narrow the window but preserve mid as a candidate.

Test case that breaks this: nums = [2, 1]

• left=0, right=1, mid=0
• nums[0]=2, nums[1]=1 → 2 > 1, so left = mid + 1 = 1
• Loop ends, returns nums[1] = 1. This one passes.

Try nums = [3, 1, 2]:

• left=0, right=2, mid=1
• nums[1]=1, nums[2]=2 → 1 <= 2, so wrong code sets right = 0
• Loop ends at left=0=right, returns nums[0]=3. Wrong answer — should be 1.

Mistake 2: Initializing mid as (left + right) / 2 in JavaScript without flooring#

In JavaScript, (left + right) / 2 gives a float. You must use Math.floor((left + right) / 2). Using a float index silently returns undefined from the array.

// WRONG in JavaScript
const mid = (left + right) / 2;       // 2.5 — not a valid index
 
// CORRECT
const mid = Math.floor((left + right) / 2);   // 2

Mistake 3: Comparing nums[mid] with nums[left] without handling the left == mid edge case#

Some solutions compare mid against left instead of right. The logic is valid, but you must add a guard: if left == mid, comparing nums[mid] against nums[left] is comparing the element to itself, which is always equal and can cause an infinite loop.

# WRONG — infinite loop when left and mid are the same index
while left < right:
    mid = (left + right) // 2
    if nums[mid] > nums[left]:    # left == mid → always False, right never moves
        left = mid + 1
    else:
        right = mid               # stuck forever

Why this happens: When right = left + 1, mid = (left + left + 1) // 2 = left. Then nums[mid] == nums[left], the condition is False, and right = mid = left never changes right. The loop never terminates.

Fix: either compare with nums[right] (the recommended approach) or use mid = (left + right + 1) // 2 (ceiling mid) when comparing with left — but this is harder to reason about. Just use nums[right].

Bonus Mistake 4: Forgetting that the loop termination is left < right, not left <= right#

When the loop exits at left == right, both pointers are pointing at the minimum. Returning nums[left] and nums[right] are equivalent — pick either. Using left <= right causes an off-by-one where the final state never converges.

Solutions#

Approach 1: Linear Scan — O(n) time, O(1) space#

State this in the interview before your optimal solution. It shows you understand the naive baseline and can then explain why we do better.

Python:

from typing import List
 
class Solution:
    def findMin(self, nums: List[int]) -> int:
        # Simply scan for the first drop in value.
        # The minimum is the first element that is smaller than the one before it.
        # If no drop is found, the array was never rotated — return nums[0].
        
        min_val = nums[0]          # start with the first element as candidate
        
        for i in range(1, len(nums)):
            if nums[i] < min_val:
                min_val = nums[i]  # found a smaller element — update candidate
        
        return min_val

JavaScript:

function findMin(nums) {
    // Scan for any element smaller than the current minimum.
    // Works in O(n) — useful to state as baseline before the log-n solution.
    
    let minVal = nums[0];              // start with first element as candidate
    
    for (let i = 1; i < nums.length; i++) {
        if (nums[i] < minVal) {
            minVal = nums[i];          // found a new minimum — update
        }
    }
    
    return minVal;
}

Approach 2: Binary Search — O(log n) time, O(1) space#

The expected solution for any interview. Explain the invariant before writing code.

Python:

from typing import List
 
class Solution:
    def findMin(self, nums: List[int]) -> int:
        left  = 0
        right = len(nums) - 1
        
        # Invariant: the minimum is always within [left, right].
        # Loop until the window collapses to a single element.
        while left < right:
            mid = (left + right) // 2  # integer division — no float risk in Python
            
            if nums[mid] > nums[right]:
                # Mid is in the elevated left segment.
                # The dip (minimum) must be strictly to the right of mid.
                # Safe to discard everything from left to mid inclusive.
                left = mid + 1
            else:
                # nums[mid] <= nums[right]:
                # Mid is in the lower right segment, OR mid IS the minimum.
                # The minimum is at mid or to the left of mid.
                # Keep mid as a candidate — do NOT use right = mid - 1.
                right = mid
        
        # When left == right, both pointers sit on the minimum.
        return nums[left]

JavaScript:

function findMin(nums) {
    let left  = 0;
    let right = nums.length - 1;
    
    // Invariant: the minimum is always within [left, right].
    // Loop until the window collapses to a single element.
    while (left < right) {
        // Use Math.floor to avoid float index — critical in JavaScript
        const mid = Math.floor((left + right) / 2);
        
        if (nums[mid] > nums[right]) {
            // Mid is in the elevated left segment.
            // The rotation point (minimum) is strictly to the right of mid.
            // Discard left half including mid.
            left = mid + 1;
        } else {
            // nums[mid] <= nums[right]:
            // Mid could be the minimum, or the minimum is left of mid.
            // Preserve mid as a candidate — shrink from the right.
            right = mid;
        }
    }
    
    // left === right — both point at the minimum element.
    return nums[left];
}

Walking through the solution out loud in an interview:

1. "I'll maintain a search window [left, right] that always contains the minimum."
2. "At each step I compare nums[mid] with nums[right]."
3. "If nums[mid] > nums[right], the minimum is to the right — move left past mid."
4. "Otherwise, mid is a candidate or the min is left of mid — shrink right to mid."
5. "When left == right, the window has one element — that's the minimum."

This narration demonstrates you understand the why, not just the what.

Complexity Analysis#

For the binary search approach: in the worst case, the window halves at every step. Starting from n elements, it takes at most log2(n) steps before left == right. With n up to 5000, that is at most 13 comparisons. For n up to 10^9 (hypothetically), that is still only 30 comparisons. The log n behavior is what makes binary search so powerful.

Follow-up Questions#

LC 154 — Find Minimum in Rotated Sorted Array II (with duplicates)#

The twist: The array may now contain duplicate elements.

Why it breaks the simple solution: Consider nums = [3, 3, 1, 3]. Here nums[mid] = nums[1] = 3 and nums[right] = nums[3] = 3. They are equal — we cannot determine which side the minimum is on. The minimum (1) is to the right, but we cannot prove that from equality alone.

The fix: When nums[mid] == nums[right], we cannot eliminate either half. We can only shrink right by one — right -= 1 — and repeat.

Python:

from typing import List
 
class Solution:
    def findMin(self, nums: List[int]) -> int:
        left  = 0
        right = len(nums) - 1
        
        while left < right:
            mid = (left + right) // 2
            
            if nums[mid] > nums[right]:
                left = mid + 1          # min is strictly to the right
            elif nums[mid] < nums[right]:
                right = mid             # mid is a candidate, or min is left of mid
            else:
                # nums[mid] == nums[right]:
                # Cannot determine which half has the minimum.
                # Shrink right by one and try again.
                right -= 1
        
        return nums[left]

Complexity with duplicates: Average O(log n), worst case O(n). The worst case is an array like [2, 2, 2, 2, 2, 0, 2] where almost all elements are equal — we shrink one step at a time.

JavaScript:

function findMinWithDuplicates(nums) {
    let left  = 0;
    let right = nums.length - 1;
    
    while (left < right) {
        const mid = Math.floor((left + right) / 2);
        
        if (nums[mid] > nums[right]) {
            left = mid + 1;             // min is strictly to the right
        } else if (nums[mid] < nums[right]) {
            right = mid;                // mid is a candidate
        } else {
            // nums[mid] === nums[right]: cannot eliminate either half
            right -= 1;                 // conservatively shrink from the right
        }
    }
    
    return nums[left];
}

LC 33 — Search in Rotated Sorted Array#

The twist: Instead of finding the minimum, find a target value and return its index (or -1).

The connection: Once you understand LC 153, LC 33 is a two-step problem:

1. Find the rotation index (the index of the minimum) using LC 153's binary search.
2. Determine which of the two sorted segments contains the target.
3. Run a standard binary search on that segment.

Alternatively, do it in a single binary search pass by determining at each step which half is sorted and whether the target falls in that half.

Single-pass approach (Python):

from typing import List
 
class Solution:
    def search(self, nums: List[int], target: int) -> int:
        left  = 0
        right = len(nums) - 1
        
        while left <= right:
            mid = (left + right) // 2
            
            if nums[mid] == target:
                return mid              # found it
            
            # Determine which half is sorted
            if nums[left] <= nums[mid]:
                # Left half [left..mid] is fully sorted
                if nums[left] <= target < nums[mid]:
                    right = mid - 1     # target is in the sorted left half
                else:
                    left  = mid + 1     # target is in the right half
            else:
                # Right half [mid..right] is fully sorted
                if nums[mid] < target <= nums[right]:
                    left  = mid + 1     # target is in the sorted right half
                else:
                    right = mid - 1     # target is in the left half
        
        return -1   # target not found

Single-pass approach (JavaScript):

function search(nums, target) {
    let left  = 0;
    let right = nums.length - 1;
    
    while (left <= right) {
        const mid = Math.floor((left + right) / 2);
        
        if (nums[mid] === target) return mid;   // found it
        
        // Determine which half is sorted
        if (nums[left] <= nums[mid]) {
            // Left half is sorted — check if target falls in it
            if (nums[left] <= target && target < nums[mid]) {
                right = mid - 1;        // target is in sorted left half
            } else {
                left  = mid + 1;        // target is in right half
            }
        } else {
            // Right half is sorted — check if target falls in it
            if (nums[mid] < target && target <= nums[right]) {
                left  = mid + 1;        // target is in sorted right half
            } else {
                right = mid - 1;        // target is in left half
            }
        }
    }
    
    return -1;  // target not found
}

Interview tip: Interviewers often move from LC 153 directly to LC 33 in the same session. Knowing the connection — "LC 33 is the same rotation insight, but now I also check which sorted half contains the target" — signals fluency with the pattern, not just memorization.

This Pattern Solves#

The core skill from LC 153 — identifying which half to eliminate based on a comparison at the boundary — applies across a family of problems:

The unifying theme: binary search is applicable whenever you can guarantee that the answer lies in one specific half of your current window. The window does not need to be sorted — it just needs to give you a clear signal about which direction to go.

Key Takeaways#

• LeetCode 153 — Find Minimum in Rotated Sorted Array is a Medium asked at Google, Microsoft, and Amazon; binary search works because one half is always sorted.
• Compare nums[mid] with nums[right] (not nums[left]) — this correctly identifies which side the minimum is on and handles the non-rotated case.
• When nums[mid] > nums[right]: minimum is in the right half, set left = mid + 1.
• When nums[mid] <= nums[right]: minimum is in the left half (or at mid), set right = mid (not mid - 1 — mid is a candidate).
• Time O(log n), space O(1) — same as standard binary search but with rotated-array boundary logic.
• The key insight: binary search doesn't need a fully sorted array — it only needs a reliable way to eliminate half the search space each step.
• With duplicates (LC 154): when nums[mid] == nums[right], you cannot determine which half to eliminate — decrement right by 1 (worst case O(n)).

Previous: Problem 36 — Rotate Array | Next: Problem 38 — Top K Frequent Elements