Matrix & grid techniques
📖 Walk me through it — plain English
A matrix (also called a grid) is just a table of numbers arranged in rows and columns. We point at a single box with two indices: r for which row (counting from the top, starting at 0) and c for which column (counting from the left, starting at 0). So m[r][c] means "the value in row r, column c." This lesson is a toolkit of four classic grid moves; the one we'll trace by hand is the sorted-matrix search, because it has the prettiest trick.
Here the matrix is sorted two ways at once: every row goes left-to-right small→large, and every column goes top-to-bottom small→large. We want to answer "is the number target somewhere in this grid?" The naive way checks all m×n boxes. The clever way needs only about m+n checks by starting in exactly the right spot.
Analogy: imagine a library where books get more expensive as you walk right along a shelf, and shelves get more expensive as you walk down. Stand at the top-right book — the priciest of the cheapest shelf. If it's still too expensive for your budget, the whole column under it is even pricier, so cross off that entire column (step one shelf-position left). If it's too cheap, the whole row to its left is even cheaper, so cross off that entire row (step down to a pricier shelf). Each look throws away a full line. The top-right corner is special because its left neighbor is smaller and its bottom neighbor is larger — the two directions disagree, which is what lets one comparison decide everything. (The top-left corner is useless: both neighbors are bigger, so a comparison can't rule anything out.)
Let's search for target = 5 in this 3×3 grid. The rows are [1,4,7], [2,5,8], [3,6,9]. We begin at r=0, c=2 (top row, rightmost column).
Why it's fast: every comparison moves us either one step left or one step down, and we never go back. Left moves can happen at most n times (the number of columns) and down moves at most m times (the number of rows), so we make at most m+n checks total — that's O(m+n), far better than scanning all m·n boxes. The same staircase idea powers the lesson's other three moves: in each, you pick the position (a shrinking wall for spiral, the main diagonal for rotate, the margins for set-zeroes) where one action does the most work with the least extra memory.
A 2-D grid is just an array of rows, but the interview value is in manipulating it without spilling into a second matrix and in exploiting structure to beat the brute-force scan. Four moves cover almost everything you'll see. First, boundary-pointer traversal: keep four walls — top, bottom, left, right — and peel one edge at a time, shrinking the box inward until it collapses (that's spiral order). Second, rotate in place: rotating an image 90° clockwise is the same as transpose, then reverse each row — transposing reflects across the main diagonal so cell (i,j) swaps with (j,i), and reversing the rows flips that reflection into a true rotation. Third, markers in the margins: to zero out whole rows/columns in O(1) extra space, reuse the first row and first column as a scratchpad of "this line is doomed" flags instead of allocating sets. Fourth, corner walk: in a matrix sorted both left-to-right and top-to-bottom, start at the top-right corner — from there every comparison eliminates an entire row or an entire column, giving O(m+n). The unifying idea: pick the position where each decision throws away the most work.
- "Rotate / transpose / reflect the image" — and in place
- "Return elements in spiral order"
- "Set entire row and column to zero" with an O(1) space ask
- Matrix sorted along both rows and columns; "does target exist?"
- Any "no extra matrix" / constant-space constraint on a grid
- Spiral: shrink top/bottom/left/right walls inward
- Rotate 90° CW: transpose, then reverse each row
- Set-zeroes: first row + first col as marker storage, plus two boolean flags
- Sorted search: walk from top-right, go left or down
def rotate(m):
n = len(m)
# 1) transpose: reflect across the main diagonal
for i in range(n):
for j in range(i + 1, n): # j > i only, or you swap back
m[i][j], m[j][i] = m[j][i], m[i][j]
# 2) reverse each row -> turns the reflection into a CW rotation
for row in m:
row.reverse()
return m # mutated in place; [[1,2,3],[4,5,6],[7,8,9]] -> [[7,4,1],[8,5,2],[9,6,3]]function rotate(m: number[][]): void {
const n = m.length;
// 1) transpose: reflect across the main diagonal
for (let i = 0; i < n; i++) {
for (let j = i + 1; j < n; j++) { // j > i only
[m[i][j], m[j][i]] = [m[j][i], m[i][j]];
}
}
// 2) reverse each row -> CW rotation
for (const row of m) row.reverse();
}In a row- and column-sorted matrix, the top-right corner is the only one where the two directions disagree: everything to its left is smaller, everything below is larger. So one comparison always rules out a full line — if cur > target the whole current column is too big (move left); if cur < target the whole current row is too small (move down). The bottom-left corner works symmetrically. The top-left and bottom-right corners are useless: both neighbors move the same way, so a comparison can't eliminate a line. That's why this runs in O(m+n), not O(m·n):
def search_matrix(m, target):
r, c = 0, len(m[0]) - 1 # start at top-right
while r < len(m) and c >= 0:
if m[r][c] == target: return True
if m[r][c] > target: c -= 1 # drop this column
else: r += 1 # drop this row
return False- Rotate: O(n²) time, O(1) space. It assumes a square matrix — transpose-then-reverse only rotates in place when rows == cols. For an m×n rectangle you must allocate a fresh n×m result.
- Rotate transpose bound: loop j from i+1, not 0. Visiting every (i,j) swaps each pair twice and undoes the transpose.
- Counter-clockwise is the mirror recipe: transpose then reverse each column (or reverse rows first, then transpose).
- Spiral: O(m·n) time, O(1) extra. After consuming the top row and right column, re-check top <= bottom before the bottom row and left <= right before the left column — otherwise a single leftover row or column gets emitted twice.
- Set-zeroes bookkeeping order: compute the row0_has_zero / col0_has_zero flags first; then mark using the first row/col; then zero the interior from those markers; then zero row 0 and column 0 last using the flags. Zeroing the margins early would corrupt the markers you still need to read.
- Sorted search: start top-right (or bottom-left), never top-left/bottom-right — those corners can't eliminate a line, collapsing you back to O(m·n). This needs full row+column sortedness; if only each row is sorted and rows are independent, binary-search each row in O(m log n) instead.
Search a row-and-column sorted matrix — write it and run it live: