Matrix

01 / The shared mechanism

A matrix isn't a single sequence — it's a 2-D coordinate space where every cell is addressed by two indices that compose in specific ways. The job is finding the right walk order. Three classic sub-patterns: rotate by transpose-then-reverse, spiral by shrinking-boundary loops, and staircase search by walking from a corner where the answer is monotone in both directions.

01 / The one-sentence essence

Start at the top-right corner. Comparing the current cell with the target tells you to go left (the whole column is too big) or down (the whole row is too small). Each step eliminates a full row or column, so the walk is O(R + C) instead of O(R · C).

Problemfind target in a row+col sorted matrixR×C3×3target5

Matrix is 3×3. Start at the top-right corner (0, 2). Target 5.

step

0 / 6

status

searching

0 / 6

rows ; … | target

02 / The pattern signature

# start at top-right; rows and cols both sorted ascendingi ← 0;  j ← C − 1while i < R and j ≥ 0:if mat[i][j] == target: return (i, j)elif mat[i][j] > target: j ← j − 1  # column too big — drop itelse: i ← i + 1 # row too small — drop itreturn (−1, −1)  # walked off the grid

03 / When to recognize this pattern

"sorted along both rows and columns"

LC 240 — the canonical Search a 2-D Matrix II. Each row is sorted left-to-right and each column is sorted top-to-bottom, but rows don't chain into one big sorted array. Staircase search is the right answer; binary search isn't.

"search 2-D matrix where each row sorted, first of next row > last of prev"

LC 74 — looks similar but it's the lookalike pitfall. The extra constraint (row breaks line up monotonically) means the whole grid behaves as one sorted array — flat binary search in O(log(R · C)) beats staircase. Use the shape of the sort, not the dimensions.

"k-th smallest in sorted matrix"

LC 378 — same row-and-column monotone structure, different question (rank instead of membership). The staircase walk generalizes: from a corner, count how many cells are ≤ x in O(R + C), then binary-search on x.

"count pairs with property in sorted grid"

Any time you have a 2-D grid where one axis monotonically increases the value and the other monotonically decreases it, a single staircase walk visits every relevant boundary cell. Counting pairs (i, j) with A[i] + B[j] < T on sorted arrays is the same shape.

04 / Common pitfalls

Starting from the top-left or bottom-right corner.

Those corners are the smallest and largest values — both neighbours go the same direction (either both larger or both smaller), so a single comparison can't tell you which axis to retreat on. Only top-right and bottom-left have the “one neighbour bigger, one neighbour smaller” property that makes the staircase work.

ii.

Confusing LC 74 (row-wrap sorted) with LC 240 (row+column sorted).

LC 74 guarantees the first element of each row is greater than the last element of the previous row — the matrix flattens into one sorted array, so the right tool is binary search over R · C indices. LC 240 only guarantees row-sorted and column-sorted independently, with no relationship between the row ends — that extra weakness is what forces staircase. Read the constraint, not just the picture.

iii.

Forgetting the loop bounds when i == R or j < 0.

The walk terminates when you walk off the top or right edge — at that point the target isn't in the matrix, so return (−1, −1) (or false). Loops that test only one bound or off-by-one the column index either miss valid answers in the last column or crash on out-of-range access. Both i < R and j ≥ 0 must guard every iteration.

05 / Go practice — on LeetCode

Four problems. The first is the textbook staircase walk; the second is the look-alike that wants binary search instead; the last two reuse the same monotone-grid structure for ranking and counting.

01Search a 2-D Matrix II— LC 240medium→02Search a 2-D Matrix— LC 74medium→03Kth Smallest Element in a Sorted Matrix— LC 378medium→04Kth Smallest Number in Multiplication Table— LC 668hard→

— / When to use which

rotate in place

Use when the question is about a geometric transform of the grid itself — 90° / 180° rotation, transpose, mirror. Decompose into two passes (transpose + row-reverse) so it's in place with no extra grid.

transpose + reverse · LC 48

spiral traversal

Use when you have to visit every cell along the perimeter of a shrinking rectangle — output in spiral order, fill in spiral order, count layers. Maintain four boundaries that collapse inward each lap.

four boundaries · LC 54 · LC 59

staircase search

Use when the matrix is monotone along both rows and columns and you're looking for a value. Start from a corner where one direction strictly increases and the other strictly decreases — every comparison rules out a full row or column.

top-right walk · LC 240 · O(N + M)