Find Minimum in Rotated Sorted Array

mediumTests passed 2026-11-11v1.0.0

TC: O(log N)|SC: O(1)

Binary Search Original Statement (leetcode).md

1. Core Invariant / The Trick

Compare `nums[mid]` strictly against `nums[r]` (the right boundary): if `nums[mid] > nums[r]`, the inflection point is strictly to the right (`l = mid + 1`); otherwise `mid` could be the minimum (`r = mid`).

2. Complexity Bounds & Proof

In any rotated array of distinct elements, comparing against `nums[r]` cleanly handles both unrotated (`nums[0] < nums[n-1]`) and rotated configurations.

3. Minimal Idiomatic Code

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

4. Failure Modes & Interview Follow-ups

Pitfalls:- Comparing against `nums[l]` fails cleanly when the remaining slice is unrotated!

Follow-ups:- Array with duplicates: decrement `r--` when `nums[mid] == nums[r]`, worst case O(N).

Personal Notes & Scratchpad (Local-First Yjs CRDT)

Saved instantaneously in IndexedDB. Streams live across peers via Hocuspocus when signed in.

Related Invariants

Search in Rotated Sorted Array (O(log N))

Browser Scratchpad

Console Output

Click Run or press Cmd/Ctrl+Enter to execute locally in a Web Worker.