Matrix search (sorted grid)

O(m+n)

Start at a corner of a row- and column-sorted matrix (top-right works well) and compare against the target: drop the column if too big, drop the row if too small. Each comparison eliminates a whole row or column.

Signals

matrix sorted along both rows and columnssearch for a value in a 2D sorted gridstart from a corner and eliminate a row or columnrow and column both monotonic

Template

function searchMatrix(matrix, target) {
    let row = 0;
    let col = matrix[0].length - 1;
    while (row < matrix.length && col >= 0) {
        const v = matrix[row][col];
        if (v === target) return true;
        if (v > target) col--;
        else row++;
    }
    return false;
}

Looks similar, isn't

Binary search (array): Binary search halves a single sorted 1-D array by index. A row- and column-sorted matrix has no single sorted order to binary-search over, so the staircase walk starts at a corner and drops a whole row or column each step, reaching the target in O(m+n) instead.

grid up to ~1e3 x 1e3, one corner walk dropping a row or column each step -> O(m+n): far below the O(mn) of scanning every cell.

Learn this pattern