Search a 2D Matrix

Starting at the top-right corner, each comparison eliminates either a row or a column. If the current value exceeds the target, the entire column to the right is useless, so move left. If it is smaller, the entire row above is useless, so move down.

Full solution

Binary search per row: each row is sorted, so a range check plus one binary search settles whether the target can be in it, giving O(m log n) with nothing to reason about beyond a standard binary search.

from bisect import bisect_left


def search_matrix(matrix: list[list[int]], target: int) -> bool:
    for row in matrix:
        # rows are sorted, so a binary search answers "is target in this row"
        if not row or target < row[0] or target > row[-1]:
            continue
        i = bisect_left(row, target)
        if i < len(row) and row[i] == target:
            return True
    return False

function searchMatrix(matrix, target) {
  for (const row of matrix) {
    // rows are sorted, so a binary search answers "is target in this row"
    if (row.length === 0 || target < row[0] || target > row[row.length - 1]) continue;
    let lo = 0;
    let hi = row.length - 1;
    while (lo <= hi) {
      const mid = (lo + hi) >> 1;
      if (row[mid] === target) return true;
      if (row[mid] < target) lo = mid + 1;
      else hi = mid - 1;
    }
  }
  return false;
}

The theory behind it

Matrix — the ground this problem stands on. All Matrix problems

What Matrix is

A matrix is a flat grid of cells laid out in rows and columns, like a checkerboard or a spreadsheet. Each cell has an address made of two numbers: its row index going down and its column index going across. Because computer memory stores these rows one after another or as arrays of arrays, jumping straight to any individual cell takes the same tiny fraction of time no matter where it sits on the board.

When to reach for it

Reach for matrix techniques when the input is a two-dimensional grid, board, or map. Common prompts include walking through a maze, finding connected islands of land in water, rotating an image ninety degrees in place, or reading numbers in a spiral. Words like rows, columns, neighbors, adjacent squares, or diagonal lines are clear signs. It also appears in grid planning where each cell depends on the values above and to the left.

How the pattern works

Think of navigating the grid using directional coordinate offsets. Define row and column step arrays for moving up, down, left, and right. Always check that new row and column indices stay strictly between zero and the board boundaries before reading cell values. For spiral scans, track four boundary lines for top, bottom, left, and right, shrinking them inward after reading each side. When searching connected regions, mark visited cells directly or write a marker value into the cell to avoid looping.