Matrix crash course ↗ · 179

240. Search a 2D Matrix II

Each row is sorted left-to-right and each column top-to-bottom, but the grid is notone flattened sorted array — so the LC 74 binary-search trick fails. Stand at the top-right corner instead: if the cell is too big move left, if too small move down. Each step kills a whole row or column in O(m + n).

● MediumBinary SearchMatrixStaircase SearchTypeScript

PROBLEM What we're solving

Given an m × n matrix where every row is sorted left-to-right and every column is sorted top-to-bottom, decide whether target appears. Return true or false.

Concrete example. 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]]

Target = 5 → true (row 1, col 1). Target = 20 → false.

KEY IDEA The top-right corner is a decision pivot

Insight → Pick a corner where the two directions disagree. At the top-right cell, moving left always gives a smaller value (row sorted) and moving down always gives a larger value (column sorted). So one comparison tells you which way to go, and the cell you leave behind can be discarded along with its entire row or column. You sweep a monotone staircase from top-right to bottom-left, eliminating one row or one column per step → O(m + n).

RECIPE Stand top-right, then walk left or down

0 · Anchor at top-right. r = 0, c = cols − 1. This is the only cell that is the max of its row and the min of its column.
1 · Read the current cell. val = matrix[r][c].
2 · Equal ⇒ done. If val === target return true.
3 · Too big ⇒ go left. If val > target, every cell below in this column is even bigger, so the whole column is useless — c−−.
4 · Too small ⇒ go down. If val < target, every cell to the left in this row is even smaller, so the whole row is useless — r++.
5 · Off the grid ⇒ absent. When r falls off the bottom or c off the left, return false.

Classic confusion → this matrix is not globally sorted, so you cannot flatten it and binary-search a single m·nrange like LC 74. The first element of a row can be smaller than the last element of the previous row (here row 3 starts at 10 while row 2 ends at 22). Reaching for the flat binary search here gives wrong answers. Use the staircase walk.

COST Complexity & alternatives

Scan every cell

O(m · n)

Ignores the sorted structure entirely.

Top-right staircase

O(m + n)

O(1) space; each step drops a full row or column.

Why not binary search per row?

Binary-searching each of the m rows is O(m log n) — correct, but worse than the staircase walk when m and n are comparable, and it throws away the column ordering. The staircase exploits both sort directions at once for a clean linear-in-the-perimeter bound.

Pattern transfer →the "stand at a corner where directions disagree" trick (a.k.a. saddleback / staircase search) recurs in Count Negative Numbers in a Sorted Matrix, Kth Smallest Element in a Sorted Matrix (as a building block), and any grid sorted along two axes.

RUN IT Staircase walk from the top-right corner

Matrix (rows separated by ;)target =

step 0 / 5

STARTStart at the top-right corner [0,4]. Everything below it is larger; everything to its left is smaller — so each comparison can discard a whole row or column.

1function searchMatrix(matrix: number[][], target: number): boolean {
2  const rows = matrix.length;
3  const cols = matrix[0].length;
4 
5▶  // Start at the TOP-RIGHT corner.
6▶  let r = 0;
7▶  let c = cols - 1;
8 
9  while (r < rows && c >= 0) {
10    const val = matrix[r][c];
11    if (val === target) return true;
12    if (val > target) c--;   // too big: drop the column, move left
13    else r++;                // too small: drop the row, move down
14  }
15  return false;
16}

State
target: 5
r (row): 0
c (col): 4
matrix[r][c]: 15
init: top-right

current celleliminated row / columnmatch found

slowfast

TYPESCRIPT The solution, annotated

searchMatrix.ts
function searchMatrix(matrix: number[][], target: number): boolean {
  const rows = matrix.length;
  const cols = matrix[0].length;

  // Start at the TOP-RIGHT corner.
  let r = 0;
  let c = cols - 1;

  while (r < rows && c >= 0) {
    const val = matrix[r][c];
    if (val === target) return true;
    if (val > target) c--;   // too big: drop the column, move left
    else r++;                // too small: drop the row, move down
  }
  return false;
}

Reading it block by block

Lines 2–3 — read dimensions. rows and colsbound the walk. (In production you'd guard an empty matrix first.)

Lines 6–7 — anchor top-right. r = 0, c = cols - 1. This corner is the unique cell that is simultaneously the largest in its row and the smallest in its column, which is what makes the next comparison decisive.

Line 9 — stay in bounds. Loop while r is above the bottom and c is right of the left edge. Falling off either side means the target is absent.

Lines 10–11 — exact hit. If matrix[r][c] === targetwe're done — return true.

Line 13 — too big, go left. val > target means every cell beneath it in column c is also too big, so the column is dead — decrement c.

Line 14 — too small, go down. val < target means every cell to the left in row r is also too small, so the row is dead — increment r.

Line 16 — exhausted. The loop ends only after eliminating every row and column that could contain target; return false.

Complexity → O(m + n) time — each iteration moves strictly left or strictly down, so at most m + n steps before walking off the grid. O(1) space — only two index variables.

INTERVIEWFollow-ups they'll ask

"Why not flatten and binary-search like LC 74?" Because this matrix is notglobally sorted — a row can start lower than the previous row ended, so the flat sequence isn't monotonic.
"Could you start at the bottom-left instead?"Yes — it's symmetric. From bottom-left, move up when too big and right when too small. The top-left and bottom-right corners do not work (both directions agree).
"Return the position, not just a boolean?" Return [r, c] at the match instead of true, and a sentinel like [-1, -1] on exhaustion.
"Count occurrences of target?"The staircase finds one hit; because values can repeat across the grid you'd continue the walk (or expand locally) rather than returning early.
"Compare to binary-search-per-row?" O(m log n) vs O(m + n); the staircase wins when the matrix is roughly square and uses both sort axes.

OPTIMAL Binary Search

searchMatrix.ts
function searchMatrix(matrix: number[][], target: number): boolean {
  const rows = matrix.length;
  const cols = matrix[0].length;

  // Start at the TOP-RIGHT corner.
  let r = 0;
  let c = cols - 1;

  while (r < rows && c >= 0) {
    const val = matrix[r][c];
    if (val === target) return true;
    if (val > target) c--;   // too big: drop the column, move left
    else r++;                // too small: drop the row, move down
  }
  return false;
}

Complexity → O(m + n) time — each iteration moves strictly left or strictly down, so at most m + n steps before walking off the grid. O(1) space — only two index variables.

ALT 1 Brute force — scan every cell

O(m·n) time · O(1) space

Ignore the sorted structure and check all m·n cells, returning true on the first match.

approach-2.ts
function searchMatrix(matrix: number[][], target: number): boolean {
  for (const row of matrix) {
    for (const val of row) {
      if (val === target) return true;
    }
  }
  return false;
}

Note → Always correct but visits every element. The staircase walk uses the row/column ordering to finish in O(m + n).

ALT 2 Binary search each row

O(m log n) time · O(1) space

Each row is individually sorted, so binary-search the target within every row.

approach-3.ts
function searchMatrix(matrix: number[][], target: number): boolean {
  const cols = matrix[0].length;
  for (const row of matrix) {
    let lo = 0;
    let hi = cols - 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;
}

Note → Correct and uses the row sort, but ignores the column sort and is O(m log n) — worse than the O(m + n) staircase for roughly square matrices.

MNEMONIC The one-liner

"Stand top-right: too big go left, too small go down."

TRIGGERS When you see _ → reach for _

matrix sorted by row AND by column, but not globally	top-right staircase walk, O(m+n)
one comparison should kill a whole row or column	start at a corner where directions disagree
current cell > target	move left (c--): drop the column
current cell < target	move down (r++): drop the row

SKELETON The reusable shape

skeleton.ts
function searchMatrix(matrix: number[][], target: number): boolean {
  let r = 0, c = matrix[0].length - 1;       // top-right
  while (r < matrix.length && c >= 0) {
    const v = matrix[r][c];
    if (v === target) return true;
    if (v > target) c--;                       // move left
    else r++;                                  // move down
  }
  return false;
}

FLASHCARDS Tap to flip

Where do you start the search and why?

Top-right corner — it is the max of its row and the min of its column, so one comparison decides whether to drop the column (move left) or the row (move down).

tap to flip

1 / 7

Answer to reveal explanations. No penalty for retries.Score: 0 / 9

QUESTION 01

Optimal time complexity of the staircase search?

QUESTION 02

Why does the LC 74 flat binary-search trick FAIL here?

QUESTION 03

You start at the top-right cell. If matrix[r][c] > target, you should:

QUESTION 04

If matrix[r][c] < target at the current cell, you should:

QUESTION 05

Which starting corner does NOT work for the staircase walk?

QUESTION 06

For the default matrix and target = 20, the walk eventually returns:

QUESTION 07

How does the staircase search compare to binary-searching each row?

QUESTION 08

#240 · Search a 2D Matrix IIEach row and column is sorted but the matrix is not globally sorted, so the flatten trick fails. Start at the top-right corner and walk a staircase — move left when too big, down when too small — for O(m+n) search.Which algorithmic approach does this primarily use?

QUESTION 09

PROBLEM What we're solving

KEY IDEA The top-right corner is a decision pivot

RECIPE Stand top-right, then walk left or down

COST Complexity & alternatives

Why not binary search per row?

RUN IT Staircase walk from the top-right corner

TYPESCRIPT The solution, annotated

Reading it block by block

INTERVIEWFollow-ups they'll ask

OPTIMAL Binary Search

ALT 1 Brute force — scan every cell

ALT 2 Binary search each row

MNEMONIC The one-liner

TRIGGERS When you see ___ → reach for ___

SKELETON The reusable shape

FLASHCARDS Tap to flip

TRIGGERS When you see _ → reach for _