Matrix

Two-dimensional arrays: index maps, traversal orders, rotation, spiral order, sorted-matrix search, in-place updates, grids as graphs and 2D prefix sums.

Overview

A matrix problem is an array problem with two indices. Almost every one reduces to a small set of moves: map (row, col) to something else, walk the cells in a fixed order, or treat each cell as a graph node. Watch for clean index math, correct bounds on non-square grids and in-place updates that do not read values they already overwrote.

Indices and neighbors

Write grid[r][c] with r the row (0 to m - 1) and c the column (0 to n - 1). Say m and n out loud, and ask whether the grid can be empty or non-square.

2D to 1D (row-major) — i = r * n + c
1D to 2D — r = i // n, c = i % n
in bounds — 0 r, or each pair swaps twice and nothing changes.

Spiral order

Keep four boundaries: top, bottom, left and right. Walk right along the top row, down the right column, left along the bottom row and up the left column, moving the matching boundary inward after each side.

Trace on a 3 x 4 grid holding 1 to 12 row by row.

right — 1 2 3 4 — 1, 2, 0, 3
down — 8 12 — 1, 2, 0, 2
left — 11 10 9 — 1, 1, 0, 2
up — 5 — 1, 1, 1, 2
right — 6 7 — 2, 1, 1, 2
down — none, top > bottom — 2, 1, 1, 1

Result: 1 2 3 4 8 12 11 10 9 5 6 7. Without the top > 1.

Grids are graphs

When the question asks about regions, islands, paths or distances, each cell is a node joined to its 4 (or 8) neighbors. Run DFS or BFS from each unvisited cell of interest.

Mark a cell visited when you push it, not when you pop it, or it can enter the queue several times. BFS gives shortest paths in steps; multi-source BFS starts with many cells in the queue at once (Rotting Oranges, distance to the nearest building). Recursive DFS on a 1000 x 1000 grid can exceed Python's default recursion limit, so prefer an explicit stack or BFS there. The Graphs topic covers these searches in depth.

2D prefix sums

To answer many 'sum of this rectangle' queries, precompute P, where P[r+1][c+1] is the sum of the rectangle from (0, 0) to (r, c). Build each cell from three neighbors, then answer any query with four lookups (inclusion and exclusion).

build — P[r+1][c+1] = g[r][c] + P[r][c+1] + P[r+1][c] - P[r][c]
query (r1, c1) to (r2, c2) — P[r2+1][c2+1] - P[r1][c2+1] - P[r2+1][c1] + P[r1][c1]

For g = [[3, 0, 1], [5, 6, 3], [1, 2, 0]], the query from (1, 1) to (2, 2) is 21 - 4 - 9 + 3 = 11, which matches 6 + 3 + 2 + 0. Building costs O(m*n) and each query O(1).

What you will be able to do

Convert between 2D and 1D indices and write bounds and neighbor checks once.
Group cells by row, column, diagonal or ring using the right key.
Rotate a square matrix in place and return any grid in spiral order.
Pick binary search or the staircase for a sorted matrix, and explain why each is correct.
Update a grid in place without reading overwritten values, and answer rectangle sums in O(1).

When to use it

Image rotation, transpose, flip or reshape.
Spiral, diagonal or ring-by-ring traversal.
Search in a matrix sorted by rows, or by rows and columns.
Regions, islands and shortest paths on a grid (BFS or DFS).
Board validation and simulation: Sudoku, Tic-Tac-Toe, Game of Life.
Setting rows or columns based on a condition, in place.
Many rectangle-sum queries on a fixed grid (2D prefix sums).

More Coding & DSA topics

Start free on Cariara · Coding problems · System design studio