UIREADY.dev
Search a 2D MatrixLoading saved progress…

Search a 2D Matrix

Searching a 2D matrix means deciding whether a target value appears anywhere in a grid of numbers — and here the grid has a property that makes the search fast. This is LeetCode 240, Search a 2D Matrix II: you are given a matrix whose every row is sorted ascending left-to-right and whose every column is sorted ascending top-to-bottom, and you return whether target is somewhere inside. Those two sort orders are the whole point — used together they let you rule out an entire row or an entire column with a single comparison, so you never have to scan the whole grid.

Signature

search2dMatrix(matrix, target)
// matrix   number[][]  — every row ascends left-to-right, every column ascends top-to-bottom
// target   number      — the value to look for
// returns  boolean     — true if target appears in matrix, otherwise false

Examples

const matrix = [
  [1, 4, 7, 11, 15],
  [2, 5, 8, 12, 19],
  [3, 6, 9, 16, 22],
  [10, 13, 14, 17, 24],
  [18, 21, 23, 26, 30],
];

search2dMatrix(matrix, 5);   // true  — it sits at row 1, column 1
search2dMatrix(matrix, 20);  // false — 20 is within range but not in the grid
search2dMatrix([[42]], 42);  // true  — single cell, matches
search2dMatrix([], 7);       // false — empty matrix, nothing to find
search2dMatrix([[]], 7);     // false — one row with zero columns

Notes

  • Both directions are sorted — every row ascends left-to-right and every column ascends top-to-bottom. That is stronger than a single sorted order and is what the fast solution leans on.
  • Rows do not continue from one to the next — unlike the fully-flattened variant (LeetCode 74), the first value of a row can be smaller than the last value of the row above it (10 starts row 3 but 15 ends row 0), so you cannot treat the grid as one long sorted list.
  • Return a boolean — you only report presence, true or false; you do not need the coordinates.
  • Empty inputs return false — an empty matrix [] or a matrix whose rows are empty [[]] holds no values at all.
  • Target may be out of range — it can be smaller than every value or larger than every value; both cases return false.
  • Aim for O(m + n) — with m rows and n columns, a single staircase walk beats both scanning all m × n cells and binary-searching every row.

FAQ

Why does the staircase search start at the top-right corner?
The top-right cell is the largest value in its row and the smallest in its column, so one comparison with the target always rules out either that entire row or that entire column. The top-left and bottom-right corners are the min or max of both their row and column, so a comparison there eliminates at most a single cell and the walk stalls.
What is the time and space complexity?
O(m + n) time for an m-by-n matrix: each step moves either left or down and never backtracks, so the walk visits at most m + n cells. It uses O(1) extra space — just a row index and a column index.
How is this different from LeetCode 74, the other Search a 2D Matrix?
In LeetCode 74 the matrix is fully sorted as if flattened — each row's first value exceeds the previous row's last — so one binary search over all m×n cells solves it in O(log(mn)). Here (LeetCode 240) only the rows and columns are independently sorted, a weaker guarantee, so the O(m + n) staircase walk is the natural fit.
Loading editor…