Search a 2D Matrix

Signal

A 2D grid that's sorted as if it were one long sorted row wrapped at a fixed width is still just a sorted array — the trigger is the same "sorted, find a value" shape, plus a coordinate-mapping step to unwrap it back to 2D.

Approach

Don't search row-by-row. Treat the whole grid as a single sorted array of length m * n and binary search over that virtual index. To read the value at virtual index mid, map it back to row = mid // n_cols, col = mid % n_cols. Everything else is the standard binary search.

Skeleton

left, right = 0, rows * cols - 1
while left <= right:
    mid = (left + right) // 2
    val = grid[mid // cols][mid % cols]
    if val == target: return True
    if val < target: left = mid + 1
    else: right = mid - 1
return False

Solution

def search_matrix(matrix: list[list[int]], target: int) -> bool:
    if not matrix or not matrix[0]:
        return False

    rows, cols = len(matrix), len(matrix[0])
    left, right = 0, rows * cols - 1

    while left <= right:
        mid = (left + right) // 2
        val = matrix[mid // cols][mid % cols]
        if val == target:
            return True
        if val < target:
            left = mid + 1
        else:
            right = mid - 1
    return False

Complexity

O(log(m·n)) time — one binary search over the virtual flattened array. O(1) space.

Pitfalls

• Doing a binary search per row (O(m log n)) is a tempting first answer but ignores the cross-row ordering guarantee — the whole grid being one sorted sequence is what gets you to O(log(m·n)).
• Getting row/col backwards in the mid // cols, mid % cols mapping — double check against a small example before trusting it under pressure.
• This exact ordering guarantee (last of row i < first of row i+1) doesn't hold for the "each row and column sorted independently" variant (LeetCode 240) — that one needs a different approach (start from a corner and eliminate a row or column at a time), don't conflate the two.