Search a 2D Matrix

mediumTests passed 2026-11-11v1.0.0
TC: O(log(M * N))|SC: O(1)
Binary SearchOriginal Statement (leetcode).md

1. Core Invariant / The Trick

Treat the strictly row-major sorted `M x N` matrix as a flattened sorted 1D array `[0 .. M*N - 1]`, mapping index `mid` back to `(mid // N, mid % N)`.

2. Complexity Bounds & Proof

Single binary search over virtual 1D coordinates avoids two nested searches.

3. Minimal Idiomatic Code

def searchMatrix(matrix: list[list[int]], target: int) -> bool:
    rows, cols = len(matrix), len(matrix[0])
    l, r = 0, rows * cols - 1
    while l <= r:
        m = (l + r) // 2
        v = matrix[m // cols][m % cols]
        if v == target: return True
        if v < target: l = m + 1
        else: r = m - 1
    return False

4. Failure Modes & Interview Follow-ups

Pitfalls:- Note `col = mid % cols` uses `cols` (N), NOT rows (M).
Follow-ups:- Search a 2D Matrix II (rows and cols sorted independently): start at top-right staircase in O(M + N).

Personal Notes & Scratchpad (Local-First Yjs CRDT)

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

Related Invariants

Binary Search (O(log N))
Browser Scratchpad
Console Output
Click Run or press Cmd/Ctrl+Enter to execute locally in a Web Worker.