153. Find Minimum in Rotated Sorted Array (Medium)

Problem

Suppose an array of length n sorted in ascending order is rotated between 1 and n times. Given the rotated array (with unique elements), return the minimum element. The algorithm must run in $O(log n)$ .

Example

nums = [3,4,5,1,2] → 1
nums = [4,5,6,7,0,1,2] → 0
nums = [11,13,15,17] → 11 (not rotated, or rotated by n)

LeetCode 153 · Link · Medium

Try it yourself

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Go to execute. Runs via the Go Playground API.

Approach 1: Brute force, `min(nums)`

def find_min(nums: list[int]) -> int:
    return min(nums)    # L1: O(n) linear scan to find minimum

function findMin(nums: number[]): number {
    return Math.min(...nums);    // L1: O(n) linear scan to find minimum
}

func findMin(nums []int) int {
    m := nums[0]                // L1: O(n) linear scan to find minimum
    for _, x := range nums[1:] {
        if x < m {
            m = x
        }
    }
    return m
}

final class Solution {
    func findMin(_ nums: [Int]) -> Int {
        guard let result = nums.min() else {
            preconditionFailure("The input must not be empty")
        }
        return result
    }
}

Where the time goes, line by line

Variables: n = len(nums).

Line	Per-call cost	Times executed	Contribution
L1 (min scan)	$O(n)$	1	$O(n)$ ← dominates

Python’s min() / JS’s Math.min() scans all n elements unconditionally.

Complexity

Time: $O(n)$ , driven by L1 (linear scan ignoring the rotated-sorted structure).
Space: $O(1)$ .

Correct but violates the $O(log n)$ constraint.

Approach 2: Walk until the first decrease

If the array is rotated, the minimum is at the first drop. Scan linearly.

def find_min(nums: list[int]) -> int:
    for i in range(1, len(nums)):          # L1: scan, up to n-1 steps
        if nums[i] < nums[i - 1]:          # L2: O(1) drop check
            return nums[i]
    return nums[0]   # not rotated (or rotated by n), first element is minimum

function findMin(nums: number[]): number {
    for (let i = 1; i < nums.length; i++) {   // L1: scan, up to n-1 steps
        if (nums[i] < nums[i - 1]) return nums[i];  // L2: O(1) drop check
    }
    return nums[0];   // not rotated (or rotated by n), first element is minimum
}

func findMin(nums []int) int {
    for i := 1; i < len(nums); i++ {    // L1: scan, up to n-1 steps
        if nums[i] < nums[i-1] {        // L2: O(1) drop check
            return nums[i]
        }
    }
    return nums[0]  // not rotated (or rotated by n), first element is minimum
}

final class Solution {
    func findMin(_ nums: [Int]) -> Int {
        for index in 1..<nums.count where nums[index] < nums[index - 1] {
            return nums[index]
        }
        return nums[0]
    }
}

Where the time goes, line by line

Variables: n = len(nums).

Line	Per-call cost	Times executed	Contribution
L1/L2 (scan for drop)	$O(1)$	up to n-1	$O(n)$ ← dominates

Stops at the first drop, so best case is $O(1)$ (minimum at index 1), worst case $O(n)$ (not rotated, must scan the whole array).

Complexity

Time: $O(n)$ , driven by L1 (linear scan for the rotation point).
Space: $O(1)$ .

Same Big-O as Approach 1 but makes the structural observation that drives the binary search.

Approach 3: Binary search on the rotation pivot (optimal)

Compare nums[mid] to nums[hi]:

If nums[mid] > nums[hi] → the min is in the right half; move lo = mid + 1.
Otherwise → the min is in the left half including mid; move hi = mid.

When lo == hi, you’re at the minimum.

def find_min(nums: list[int]) -> int:
    lo, hi = 0, len(nums) - 1      # L1: O(1)
    while lo < hi:                  # L2: loop, O(log n) iterations
        mid = (lo + hi) // 2       # L3: O(1) midpoint
        if nums[mid] > nums[hi]:    # L4: O(1) compare to right boundary
            lo = mid + 1           # L5: O(1) min is in right half
        else:
            hi = mid               # L6: O(1) min is mid or left of mid
    return nums[lo]

function findMin(nums: number[]): number {
    let lo = 0, hi = nums.length - 1;    // L1: O(1)
    while (lo < hi) {                     // L2: loop, O(log n) iterations
        const mid = (lo + hi) >> 1;      // L3: O(1) midpoint
        if (nums[mid] > nums[hi]) lo = mid + 1;  // L4/L5: min is in right half
        else hi = mid;                            // L6: min is mid or left of mid
    }
    return nums[lo];
}

func findMin(nums []int) int {
    lo, hi := 0, len(nums)-1      // L1: O(1)
    for lo < hi {                  // L2: loop, O(log n) iterations
        mid := (lo + hi) / 2     // L3: O(1) midpoint
        if nums[mid] > nums[hi] { // L4: O(1) compare to right boundary
            lo = mid + 1         // L5: O(1) min is in right half
        } else {
            hi = mid             // L6: O(1) min is mid or left of mid
        }
    }
    return nums[lo]
}

final class Solution {
    func findMin(_ nums: [Int]) -> Int {
        var low = 0
        var high = nums.count - 1
        while low < high {
            let middle = low + (high - low) / 2
            if nums[middle] > nums[high] {
                low = middle + 1
            } else {
                high = middle
            }
        }
        return nums[low]
    }
}

Where the time goes, line by line

Variables: n = len(nums).

Line	Per-call cost	Times executed	Contribution
L1 (init)	$O(1)$	1	$O(1)$
L2/L3/L4 (loop body)	$O(1)$	log n	$O(log n)$ ← dominates
L5 or L6 (narrow)	$O(1)$	log n	$O(log n)$

Each iteration eliminates half the range. Unlike standard binary search, the loop condition is lo < hi (not lo <= hi) because we keep hi as a possible answer when the min could be at mid.

Complexity

Time: $O(log n)$ , driven by L2 (loop halves the search space each step).
Space: $O(1)$ .

Why compare to `hi`, not `lo`?

Comparing nums[mid] to nums[lo] is subtler because a not-rotated segment [lo, mid] can look identical to a rotated one starting past mid. Comparing to nums[hi] uniquely identifies which half contains the minimum.

Try this approach:

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Click Run Go to execute. Runs via the Go Playground API.

Swift notes

Swift’s min() returns an optional because an array can be empty at the type level, even though this problem promises a nonempty input. The brute-force approach unwraps that result with an explicit precondition failure. The binary-search approach relies on the stronger problem contract and indexes directly.

Summary

Approach	Time	Space
`min(nums)`	$O(n)$	$O(1)$
Linear until decrease	$O(n)$	$O(1)$
Binary search	$O(log n)$	$O(1)$

The “compare to nums[hi]” trick is the key insight; it transfers directly to problem 33 (Search in Rotated Sorted Array).

Test cases

# Quick smoke tests - paste into a REPL or save as test_153.py and run.
# Uses the optimal Approach 3 implementation.

def find_min(nums: list) -> int:
    lo, hi = 0, len(nums) - 1
    while lo < hi:
        mid = (lo + hi) // 2
        if nums[mid] > nums[hi]:
            lo = mid + 1
        else:
            hi = mid
    return nums[lo]

def _run_tests():
    assert find_min([3, 4, 5, 1, 2]) == 1
    assert find_min([4, 5, 6, 7, 0, 1, 2]) == 0
    assert find_min([11, 13, 15, 17]) == 11    # not rotated
    assert find_min([1]) == 1                  # single element
    assert find_min([2, 1]) == 1               # two elements, rotated
    assert find_min([1, 2]) == 1               # two elements, not rotated
    print("all tests pass")

if __name__ == "__main__":
    _run_tests()

function findMin(nums: number[]): number {
    let lo = 0, hi = nums.length - 1;
    while (lo < hi) {
        const mid = (lo + hi) >> 1;
        if (nums[mid] > nums[hi]) lo = mid + 1;
        else hi = mid;
    }
    return nums[lo];
}

console.assert(findMin([3, 4, 5, 1, 2]) === 1);
console.assert(findMin([4, 5, 6, 7, 0, 1, 2]) === 0);
console.assert(findMin([11, 13, 15, 17]) === 11);    // not rotated
console.assert(findMin([1]) === 1);                   // single element
console.assert(findMin([2, 1]) === 1);                // two elements, rotated
console.assert(findMin([1, 2]) === 1);                // two elements, not rotated
console.log("all tests pass");

package main

import "fmt"

func findMin(nums []int) int {
    lo, hi := 0, len(nums)-1
    for lo < hi {
        mid := (lo + hi) / 2
        if nums[mid] > nums[hi] {
            lo = mid + 1
        } else {
            hi = mid
        }
    }
    return nums[lo]
}

func main() {
    if findMin([]int{3, 4, 5, 1, 2}) != 1     { panic("test 1") }
    if findMin([]int{4, 5, 6, 7, 0, 1, 2}) != 0 { panic("test 2") }
    if findMin([]int{11, 13, 15, 17}) != 11   { panic("test 3") } // not rotated
    if findMin([]int{1}) != 1                  { panic("test 4") } // single element
    if findMin([]int{2, 1}) != 1               { panic("test 5") } // two elements, rotated
    if findMin([]int{1, 2}) != 1               { panic("test 6") } // two elements, not rotated
    fmt.Println("all tests pass")
}

Arrays, rotated-sorted invariant; binary search on the pivot

Modified Binary Search, the binary search variant for rotated, peaked, or partly ordered data.
Binary Search, the halving tactic for ordered spaces where one side can be discarded.

153. Find Minimum in Rotated Sorted Array (Medium)

Problem

Try it yourself

Approach 1: Brute force, min(nums)

Approach 2: Walk until the first decrease

Approach 3: Binary search on the rotation pivot (optimal)

Why compare to hi, not lo?

Swift notes

Summary

Test cases

Related data structures

Related concepts

Approach 1: Brute force, `min(nums)`

Why compare to `hi`, not `lo`?