#31 Medium Time O(log n) Space O(1) Animated

Find Minimum in Rotated Sorted Array

Find the minimum element in a rotated sorted array.

LeetCode ↗

Tutor Mode Build the mental model before you memorize the code.

1 Predict
2 Trace
3 Explain
4 Implement

Pattern Binary search over a monotonic decision

Each comparison proves that half of the remaining search space cannot contain the answer.

Approach: Binary Search

Click play to start

Step 0 / 0

Press play to start the visualization.

1×

Core Insight

Each comparison proves that half of the remaining search space cannot contain the answer.

Common Pitfall

Choose inclusive or exclusive bounds once and update them consistently.

Description

Find the minimum element in a rotated sorted array.

Constraints

Time Complexity: O(log n)
Space Complexity: O(1)

Solution — Binary Search

TimeO(log n) SpaceO(1)

Implementation Plan

Translate the invariant into these small, testable moves.

Set the initial bounds.
Compute a midpoint.
Use the monotonic condition to discard one half.
Return when found or when the bounds cross.

def findMin(nums):
    res = nums[0]
    l, r = 0, len(nums) - 1
    
    while l <= r:
        if nums[l] < nums[r]:
            res = min(res, nums[l])
            break
            
        m = (l + r) // 2
        res = min(res, nums[m])
        if nums[m] >= nums[l]:
            l = m + 1
        else:
            r = m - 1
            
    return res

Koko Eating Bananas

Search in Rotated Sorted Array

Find Minimum in Rotated Sorted Array

Steps

Description

Constraints

Tags

Solution — Binary Search