Matrices & 2D Grids
Why this exists
A two-dimensional array is the second data structure most programmers meet, right after the one-dimensional one, and it is the first place where index arithmetic starts to bite. Rows and columns get swapped, the boundary conditions multiply from two to four, and a surprising number of production bugs — in image filters, spreadsheet engines, game maps and scientific code — trace back to someone writing grid[c][r] once. Grids also hide the first real graph most people program against: the cells are vertices, adjacency is "shares an edge", and breadth-first search over that graph is how a paint bucket fills a region, how a game computes reachable squares, and how a robot plans around obstacles.
Historically the matrix predates the computer by a century — Sylvester coined the term in 1850 and Cayley developed the algebra in 1858 — and dense linear algebra was the first killer application of electronic computing. The way a matrix is laid out in memory (row by row in C and NumPy, column by column in Fortran and the BLAS libraries that still underpin every numerical stack) was decided by those early systems and continues to determine which loops are fast and which are ten times slower. Image processing added its own vocabulary: an image is a grid of pixels, a convolution is a sliding stencil over that grid, and flood fill was in MacPaint in 1984 as the paint bucket.
In interviews, grid problems are a genre of their own: spiral traversal, rotation in place, search in a sorted matrix, number of islands, rotting oranges, shortest path with obstacles, game of life. They test three skills at once — index discipline, boundary handling, and recognising that a grid is a graph. This page builds those skills from the representation up, proves the two index mappings people usually memorise, and shows where grid problems hand off to the graph and dynamic-programming modules.
Pattern triggers
| If the problem says or has… | Think of… |
|---|---|
| "traverse in spiral / zigzag / diagonal order" | Four shrinking boundaries; the or invariant for diagonals |
| "rotate the image by 90°", "in place" | Transpose then reverse each row, or four-way swap by layers |
| "set the entire row and column to zero", "constant space" | Use the first row and column as marker storage |
| "matrix with sorted rows and columns", "find target" | Staircase search from the top-right corner, |
| "each row sorted, first element of a row > last of previous" | Treat as one sorted array of length and binary search |
| "connected region of the same colour", "count islands", "fill" | Flood fill — DFS or BFS over 4-neighbours with a visited set |
| "minimum time / steps for something to spread from several cells" | Multi-source BFS: all sources start in the queue at distance 0 |
| "distance of every cell to the nearest X" | Multi-source BFS from all X cells |
| "shortest path from top-left to bottom-right, obstacles" | BFS (unit weights); never DFS for shortest path |
| "cells update simultaneously based on neighbours" | Encode old and new state in the same cell (two bits) to update in place |
| "count paths", "minimum path sum", "no obstacles" | Grid DP — a later module, named below |
| "coordinates up to but few points" | Coordinate compression before building any grid |
| "mostly zeros", "huge sparse matrix" | Dictionary of keys or compressed sparse row, not a dense array |
| "multiply matrices", "power of a matrix" | triple loop; fast exponentiation for powers |
The two structural triggers: if the problem mentions neighbours, it is a graph problem on a grid; if it mentions rotation, transposition, or reflection, it is an index-mapping problem and you should write the mapping down before you write code.
Intuition & first principles
Representation
A rectangular grid of rows and columns is indexed grid[r][c] with and . Row first, column second — always. The pair (r, c) is also written in mathematics, and never in this page, because x traditionally means the horizontal coordinate, which is the column, and that is exactly the swap that causes bugs.
In most languages a 2D array is one of two things:
- Rectangular, row-major, contiguous: a single block of elements where element
(r, c)lives at flat index . C arrays declaredint a[n][m], NumPy arrays by default, Java arrays conceptually (though Java actually allocates each row separately), and any "flattened" 1D vector you index by hand. The inverse of the flattening isr = idx // m,c = idx % m. - Jagged (array of arrays): an outer array of references, each pointing to a separately allocated row. Python lists of lists, Java
int[][], JavaScript arrays of arrays, C++vector<vector<int>>. Rows may have different lengths and are not adjacent in memory, so a column walk costs a pointer dereference per step.
The distinction matters for two reasons. Correctness: with a jagged array, [[0] * m] * n in Python creates references to the same row, so writing to one cell changes every row — use [[0] * m for _ in range(n)]. Performance: contiguous row-major layout means iterating for r: for c: walks memory sequentially and streams through the cache, while for c: for r: jumps elements each step and misses the cache on nearly every access once a row exceeds the cache line. On a 4096×4096 matrix of 32-bit integers the column-major loop can be several times slower than the row-major one; the mechanism is covered in How Data Structures Live in Memory. The rule: make the innermost loop vary the last index.
Direction arrays and bounds checking
Every neighbour-based grid algorithm uses the same idiom. Define the four unit steps once:
DIRS4 = [(1, 0), (-1, 0), (0, 1), (0, -1)] # down, up, right, left
DIRS8 = DIRS4 + [(1, 1), (1, -1), (-1, 1), (-1, -1)] # plus diagonals
and write a single in_bounds(r, c) test: 0 <= r < n and 0 <= c < m. Then every neighbour loop is
for dr, dc in DIRS:
nr, nc = r + dr, c + dc
if in_bounds(nr, nc) and <cell-specific test>:
...
Writing the four neighbours out by hand (grid[r+1][c], grid[r-1][c], …) quadruples the places a bounds bug can hide. The direction-array idiom reduces it to one. A frequent compact alternative is a single array d = [0, 1, 0, -1, 0] with dr = d[k], dc = d[k+1] for k = 0..3; it is equivalent and saves a few characters in contests.
The grid as an implicit graph
Take the cells as vertices and connect each cell to its in-bounds 4-neighbours (or 8-neighbours if diagonals count). That is a graph with vertices and at most undirected edges, and you never have to build it: the adjacency list of is computed from the direction array on demand. Everything in Graphs applies unchanged:
- DFS from a cell visits its connected component — that is flood fill, and counting components is "number of islands".
- BFS from a cell visits cells in order of distance, where distance is the number of steps — so BFS from the start finds the shortest path, and BFS from all sources at once finds, for every cell, the distance to the nearest source.
- Weighted grids (cost to enter a cell) make it a weighted graph: Dijkstra, or 0-1 BFS when the weights are 0 and 1.
The one thing that is different from a general graph is the visited set. In a general graph you need a hash set or a boolean array indexed by vertex id. In a grid you can use an boolean array, or — if the problem allows mutating the input — overwrite visited cells with a sentinel value (turn '1' into '0' when you visit it). The in-place version saves memory and is what most interview solutions do, but say out loud that you are mutating the input and ask whether that is acceptable.
Why DFS cannot find shortest paths
DFS explores one path as deep as it goes before backtracking. The first time it reaches the target, it has followed some path, with no guarantee of minimality — on a 3×3 open grid a DFS that happens to go right first will reach the opposite corner in 4 steps, but one that snakes down, right, up, right, down reaches it in 8, and whether you then find the 4-step path depends on whether your visited marking lets you revisit cells (which blows up the running time) or not (which locks in the bad answer). BFS visits cells in nondecreasing order of distance, so the first visit to any cell is along a shortest path. The proof is in the correctness section.
Mechanics
Row, column and diagonal traversals
Row-major traversal is for r in range(n): for c in range(m). Column-major swaps the loops. The interesting ones are diagonals.
Cells on the same anti-diagonal (running from bottom-left to top-right) share the same value of . There are such diagonals, indexed , and the cells on diagonal are for the that keep both coordinates in range: . Cells on the same main diagonal (top-left to bottom-right) share , which ranges from to ; shifting by makes it a valid array index. These two invariants are the whole trick behind "diagonal traverse" problems and behind the N-Queens attack check in Backtracking.
Zigzag (boustrophedon) order reverses every other row: for r: row = grid[r] if r % 2 == 0 else reversed(grid[r]). Zigzag diagonal traversal (LeetCode 498) alternates direction along anti-diagonals: on even go up-right (decreasing ), on odd go down-left.
Spiral order with four shrinking boundaries
Maintain top, bottom, left, right, initially 0, n-1, 0, m-1. Repeat while top <= bottom and left <= right:
- Walk the top row from
lefttoright; thentop += 1. - Walk the right column from
toptobottom; thenright -= 1. - If
top <= bottom: walk the bottom row fromrightdown toleft; thenbottom -= 1. - If
left <= right: walk the left column frombottomup totop; thenleft += 1.
The two guarded steps are the early-exit checks. Without them, a matrix with a single remaining row (after step 1 shrank top past bottom) would have its row walked a second time in reverse by step 3, and a single remaining column would be double-counted by step 4. The guards are checked after the boundary moves in steps 1 and 2, which is exactly when the last row or column may have just been consumed.
flowchart TD
S["top=0 bottom=n-1 left=0 right=m-1"] --> C{"top <= bottom and left <= right ?"}
C -->|"no"| Done["done"]
C -->|"yes"| T["walk row top, left..right, then top += 1"]
T --> R["walk column right, top..bottom, then right -= 1"]
R --> G1{"top <= bottom ?"}
G1 -->|"yes"| B["walk row bottom, right..left, then bottom -= 1"]
G1 -->|"no"| C
B --> G2{"left <= right ?"}
G2 -->|"yes"| L["walk column left, bottom..top, then left += 1"]
G2 -->|"no"| C
L --> C
Trace on the 3×4 matrix
1 2 3 4
5 6 7 8
9 10 11 12
| Round | Boundaries before the walk (top, bottom, left, right) | Walk | Cells emitted | Output so far |
|---|---|---|---|---|
| 1 | (0, 2, 0, 3) | top row → | 1, 2, 3, 4 | 1 2 3 4 |
| 1 | (1, 2, 0, 3) | right column ↓ | 8, 12 | 1 2 3 4 8 12 |
| 1 | (1, 2, 0, 2) | bottom row ← | 11, 10, 9 | 1 2 3 4 8 12 11 10 9 |
| 1 | (1, 1, 0, 2) | left column ↑ | 5 | 1 2 3 4 8 12 11 10 9 5 |
| 2 | (1, 1, 1, 2) | top row → | 6, 7 | 1 2 3 4 8 12 11 10 9 5 6 7 |
| 2 | (2, 1, 1, 2) | guard top <= bottom fails → stop | — | final |
Twelve cells, twelve emissions, each once. In round 2 the top-row walk consumed the last row; top became 2 > bottom = 1, and the guard before the right-column walk — the loop condition, in this implementation — ended the traversal. Had the bottom-row step not been guarded in a different shape (say a 3×3 whose centre is a single cell), it would have emitted the centre twice.
Generating a spiral (LeetCode 59, "Spiral Matrix II") is the same loop writing 1, 2, 3, … into the cells instead of reading them.
Transpose, rotate, reflect
Transpose swaps rows and columns: T[c][r] = A[r][c]. For a square matrix in place, swap A[r][c] with A[c][r] for all c > r — only the upper triangle, or every pair swaps twice and nothing changes.
Rotate 90° clockwise. Claim: the cell at moves to . Check it on the corners of a 3×3: top-left goes to top-right ; top-right goes to bottom-right ; bottom-left goes to top-left . A quarter-turn clockwise sends "how far down" into "how far from the right edge" — the top row becomes the right column — and sends "how far right" into "how far down" — the left column becomes the top row. In symbols: new row = old column, new column = old row.
Why transpose-then-reverse-rows works: transpose sends , and reversing each row sends . Composition: , the rotation mapping. Both steps are in place. Counter-clockwise is transpose then reverse each column (or reverse rows, then transpose). A 180° rotation is reverse rows then reverse columns.
Full mapping for a 3×3:
| Old position (r, c) | Value | New position (c, n−1−r) |
|---|---|---|
| (0, 0) | 1 | (0, 2) |
| (0, 1) | 2 | (1, 2) |
| (0, 2) | 3 | (2, 2) |
| (1, 0) | 4 | (0, 1) |
| (1, 1) | 5 | (1, 1) |
| (1, 2) | 6 | (2, 1) |
| (2, 0) | 7 | (0, 0) |
| (2, 1) | 8 | (1, 0) |
| (2, 2) | 9 | (2, 0) |
giving
1 2 3 7 4 1
4 5 6 -> 8 5 2
7 8 9 9 6 3
Rotate in place by layers. Alternatively, process the matrix as concentric rings. For layer (from 0 to ), with first = ℓ, last = n - 1 - ℓ, and for each offset i from first to last - 1, do a four-way cyclic swap: save top = A[first][i], move left → top (A[first][i] = A[last - off][first]), bottom → left, right → bottom, saved top → right, where off = i - first. Each group of four cells is rotated once; the centre cell of an odd matrix is never touched. Same time, space, and it rotates each element exactly once instead of twice, which matters for large cells (a row of pixels) or when the "cells" are expensive to move.
Non-square matrices cannot be rotated in place: an matrix rotates into an one, so the shape changes and you must allocate. Transposition in place for non-square matrices is possible (it is a permutation of the flat array) but needs cycle-following and is a classic hard problem; in practice allocate.
Reflections: horizontal (left-right mirror) is reverse each row, ; vertical (top-bottom) is reverse the row order, . The eight symmetries of the square — four rotations and four reflections — are generated by transpose and one reflection, which is useful for canonicalising board positions in game-tree search.
Set matrix zeroes in O(1) extra space
If a cell is zero, its whole row and column become zero. The naive approach (zero as you go) cascades: newly zeroed cells trigger more zeroing. Collecting row and column indices in sets costs extra space. The -space trick stores the markers in the matrix itself: use grid[0][c] as the flag "column c must be zeroed" and grid[r][0] as "row r must be zeroed". The cell grid[0][0] is shared by both, so one separate boolean (firstColZero) records the first column's state. Then:
- Scan; set the markers.
- For all
r >= 1, c >= 1: zero the cell ifgrid[r][0] == 0 or grid[0][c] == 0. - If
grid[0][0] == 0, zero the first row. IffirstColZero, zero the first column.
Order matters: the first row and first column are processed last, because they hold the markers everyone else reads.
Search in a sorted matrix
Two different problems hide under this name.
Fully sorted (each row sorted, and the first element of each row exceeds the last of the previous — LeetCode 74): the matrix read in row-major order is a sorted array of elements. Binary search on the flat index idx with r = idx // m, c = idx % m. .
Rows and columns sorted independently (LeetCode 240): row-major order is not sorted, so flat binary search fails. Use the staircase search: start at the top-right cell. If it equals the target, done. If it is greater than the target, every cell below it in that column is also greater (columns are sorted), so the whole column is eliminated — move left. If it is less, every cell to its left in that row is also less (rows are sorted), so the whole row is eliminated — move down. Each step removes a row or a column, so at most steps. Starting from the bottom-left works symmetrically; starting from the top-left does not, because both neighbours there are larger and no elimination is possible.
On the classic 5×5 matrix with rows [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], searching for 5 takes 5 steps (15 → 11 → 7 → 4 → down to 5) and searching for 20 takes 9 steps before running off the grid.
Flood fill and number of islands
Flood fill replaces a connected region of one colour with another. From the seed cell, visit every reachable cell with the same original colour and recolour it. Three implementations:
- Recursive DFS: visit cell, recolour, recurse into each same-colour neighbour. Shortest to write; recursion depth equals the longest simple path, which on a snake-shaped region is frames — a stack overflow in Python (default limit 1000) and in Java (typical default stack handles on the order of frames).
- Iterative DFS with an explicit stack: push the seed; pop, recolour, push same-colour neighbours. Same visit order modulo tie-breaking, no recursion limit.
- BFS with a queue: identical structure with a queue; visits in distance order, which flood fill does not need but costs nothing.
One subtlety: if the new colour equals the old colour, return immediately — otherwise the "same colour as original" test never fails and the fill loops forever (in the recursive version) or revisits endlessly (in the iterative one without a separate visited set).
Number of islands: scan every cell; whenever you find an unvisited land cell, increment the count and flood-fill (sink) the whole island so it is not counted again. Every cell is visited a constant number of times, so . On ["11000", "11000", "00100", "00011"] the answer is 3.
Multi-source BFS
Problems like "distance from every cell to the nearest 0" (01 Matrix, LeetCode 542) or "how many minutes until all oranges rot" (LeetCode 994) ask for distances from a set of sources. Running one BFS per source costs in the worst case. Instead, put every source into the queue at distance 0 before starting, then run one ordinary BFS. Each cell is first reached by whichever source is nearest — the standard BFS argument applied to a graph with an imaginary super-source connected to all real sources by zero-cost edges.
flowchart LR
subgraph L0["level 0 (sources)"]
A["(0,0)"]
B["(2,2)"]
end
subgraph L1["level 1"]
C["(1,0)"]
D["(0,1)"]
E["(1,2)"]
F["(2,1)"]
end
subgraph L2["level 2"]
G["(2,0)"]
H["(1,1)"]
I["(0,2)"]
end
A --> C
A --> D
B --> E
B --> F
C --> G
C --> H
E --> I
Trace on the 3×3 grid where 0 marks a source and 1 marks a cell whose distance we want:
0 1 1
1 1 1
1 1 0
Neighbours are tried in the order down, up, right, left. The queue is processed level by level.
| Level | Cells dequeued | Newly discovered (distance assigned) | Queue after the level |
|---|---|---|---|
| 0 | — | (0,0)=0, (2,2)=0 (the sources) | (0,0), (2,2) |
| 1 | (0,0), (2,2) | (1,0)=1, (0,1)=1, (1,2)=1, (2,1)=1 | (1,0), (0,1), (1,2), (2,1) |
| 2 | (1,0), (0,1), (1,2), (2,1) | (2,0)=2, (1,1)=2, (0,2)=2 | (2,0), (1,1), (0,2) |
| 3 | (2,0), (1,1), (0,2) | none | empty — done |
Resulting distance grid:
0 1 2
1 2 1
2 1 0
The centre cell is at distance 2 from both sources and is discovered once, by , which happened to be dequeued first; then sees it already visited and skips it. For rotting oranges the number of levels processed (minus one) is the answer, with a final check that no fresh orange remains unreached.
Shortest path in a grid with obstacles
Single-source BFS from the start cell over open cells; the distance at the target is the answer, or −1 if the target is never dequeued. Mark cells visited when enqueued, not when dequeued, or the same cell can be enqueued many times from different neighbours and the queue grows to with repeated work. For 8-directional movement (LeetCode 1091) use DIRS8; the path length counts cells, so the start contributes 1.
If entering a cell has a cost (a weight), BFS is wrong — a 3-step path through cheap cells may be better than a 2-step path through an expensive one — and you need Dijkstra with a priority queue, or 0-1 BFS with a deque when weights are only 0 and 1 (push to the front for 0-cost edges, to the back for 1-cost edges). These are in Graphs.
Grid DP preview
"How many paths from the top-left to the bottom-right moving only right or down" has the recurrence paths[r][c] = paths[r-1][c] + paths[r][c-1] — each cell depends on the cell above and the cell to its left, so a row-major fill computes it in . Minimum path sum, obstacles, and the many variants are the subject of Grid & Path DP in the dynamic-programming module; the point to carry forward is that the traversal order that makes the DP valid is exactly the row-major order discussed above, because dependencies point up and left.
Game of life in place
Every cell updates simultaneously from its 8 neighbours' current states. Updating in place naively would let already-updated neighbours influence later cells. The -space solution encodes two bits per cell: bit 0 is the current state, bit 1 the next state. Pass 1 reads only bit 0 of neighbours (grid[nr][nc] & 1) and writes bit 1 of the cell (grid[r][c] |= 2 when the cell will live). Pass 2 shifts every cell right by one (grid[r][c] >>= 1). Because pass 1 never changes bit 0, every neighbour read sees the original board. The idiom — "keep the old value readable while writing the new one" — generalises to any simultaneous-update cellular automaton or stencil computation; large-scale implementations use two buffers and swap them, which is the same idea with more memory and less bit-twiddling.
Large grids and coordinate compression
When coordinates range to but only a few thousand points, rectangles or segments are given, do not allocate a grid. Sort the distinct -coordinates, map each to its rank, do the same for , and work on the compressed grid where is the number of distinct values. Rectangle-area-union and "count cells covered by at least one rectangle" problems are solved this way, often with a 2D difference array from the prefix sums lesson applied to the compressed grid.
Sparse matrices
A dense matrix of doubles is 80 GB. If only entries are non-zero, store them sparsely:
- Dictionary of keys (DOK): a hash map from
(r, c)to value. Trivial to build and update, slow to traverse by row. - Compressed sparse row (CSR): three arrays —
values,col_index, androw_ptrwhererow_ptr[r]..row_ptr[r+1]is the range of entries in row . Note thatrow_ptris a prefix sum of per-row non-zero counts. Compact, fast for matrix-vector products and row traversal, costly to modify. This is what SciPy'scsr_matrixand most sparse solvers use.
Sparse matrix multiplication (LeetCode 311) is the interview version: skip zero entries of the left operand's row, which turns into .
Matrix multiplication
The product of an and a matrix is C[i][j] = Σ_t A[i][t] * B[t][j], a triple loop costing multiplications — for square matrices. Loop order matters for cache: the i, t, j ordering (with A[i][t] hoisted) streams through rows of both B and C, and is typically faster than the textbook i, j, t order, which walks a column of B. Strassen's 1969 algorithm multiplies two block matrices with 7 instead of 8 recursive products, giving ; it is used in practice only for very large matrices because of its constant factor and numerical instability. The theoretical exponent has been pushed to roughly 2.37 by a line of work culminating (as of 2024) in Williams, Xu, Xu and Zhou, but those algorithms are galactic — never faster for any matrix that fits in a computer. Production code calls BLAS GEMM, which is with aggressive blocking for the cache hierarchy and vectorisation. Fast matrix exponentiation — in by repeated squaring — is how linear recurrences such as Fibonacci are computed in logarithmic time.
The ladder: brute force → better → optimal
Number of islands
Rung 1 — re-scan after each discovery. Find a land cell, flood-fill it to water, restart the scan from the beginning. Correct, but the restart makes the worst case when there are single-cell islands.
Rung 2 — one scan with DFS marking. Scan once; when you find land, increment the count and sink the island. Each cell is visited times (once by the scan, once by a flood fill), so time and worst-case stack/queue space. This is the standard answer.
Rung 3 — Union-Find. Process cells, uniting each land cell with its land neighbours; count components at the end. Same asymptotics, more code, but it supports the dynamic version — "Number of Islands II", where cells turn into land one at a time and you must report the count after each — in near-constant amortised time per update, which DFS cannot do without re-running. Union-Find is developed in Graphs.
Rotation
Rung 1 — allocate a new matrix. B[c][n-1-r] = A[r][c]. time, space. Trivially correct and the only option for non-square matrices.
Rung 2 — transpose then reverse rows. Two in-place passes, time, space; each element moves twice.
Rung 3 — layer-by-layer four-way swap. One pass, each element moves once, space. Marginal gain in work, more index arithmetic; prefer rung 2 unless element moves are expensive.
Shortest path in a grid
Rung 1 — DFS with backtracking, trying every path. Exponential in the worst case, and the first path found is not shortest.
Rung 2 — BFS. time and space; the first time the target is reached is along a shortest path. For unit weights this is optimal: every cell might need to be looked at.
Rung 3 — A* with the Manhattan-distance heuristic. Same worst case, but on open maps with a known target it expands far fewer cells. Used in games; covered with Dijkstra in the graphs module.
| Problem | Approach | Time | Extra space | Note |
|---|---|---|---|---|
| islands | rescan after each | avoid | ||
| islands | single scan + DFS/BFS | worst (stack/queue) | standard | |
| islands | Union-Find | supports online additions | ||
| rotate | new matrix | works for non-square | ||
| rotate | transpose + reverse | two moves per element | ||
| rotate | layers | one move per element | ||
| shortest path | DFS all paths | exponential | wrong tool | |
| shortest path | BFS | optimal for unit weights | ||
| shortest path | A* | worst | fewer expansions in practice | |
| spiral | boundaries | each cell emitted once | ||
| staircase search | from top-right | rows and columns sorted | ||
| flat binary search | treat as 1D | needs fully sorted matrix |
Correctness
Spiral boundary invariant
Invariant: at the top of each loop iteration, the cells not yet emitted are exactly the sub-rectangle [top..bottom] × [left..right], and every cell outside it has been emitted exactly once.
Initially the sub-rectangle is the whole matrix and nothing is emitted; the invariant holds. Each walk emits exactly one full edge of the current sub-rectangle and then moves the corresponding boundary inward by one, so the remaining sub-rectangle is again exactly the unemitted set. The guards top <= bottom and left <= right before the third and fourth walks ensure that when the sub-rectangle has degenerated to a single row (after the top walk) or a single column (after the right walk), we do not walk it again in the opposite direction. The loop ends when the sub-rectangle is empty, i.e. all cells have been emitted once. Termination: each iteration strictly shrinks the sub-rectangle's perimeter.
Staircase search elimination
Invariant: the target, if present, lies in the sub-matrix [r..n-1] × [0..c] where is the current position.
Initially : the sub-matrix is everything. At , if M[r][c] > target: because column is sorted top to bottom, M[r'][c] >= M[r][c] > target for all , so no cell in column at or below row can be the target; combined with the invariant, the target must be in [r..n-1] × [0..c-1], and we move to . If M[r][c] < target: because row is sorted left to right, M[r][c'] <= M[r][c] < target for all , so no cell in row at or left of column can be the target, and the target must be in [r+1..n-1] × [0..c]; we move to . Each step shrinks the sub-matrix by one row or one column, so after at most steps either the target is found or the sub-matrix is empty and the target is absent.
BFS layers are distances
Sketch (full proof in Graphs): BFS dequeues vertices in nondecreasing order of their assigned distance, and every vertex is assigned a distance exactly one more than the vertex that discovered it. By induction on the distance : all vertices at true distance are discovered while processing level , because each has a neighbour at true distance , and none can be discovered earlier because that would exhibit a shorter path. For multi-source BFS, add an imaginary source connected to all real sources; its BFS distances exceed the real ones by exactly one, so the ordering argument is unchanged.
Rotation mapping
Transpose is the map . Reversing each row of an matrix is . Then sends , which is the 90° clockwise rotation: the first row goes to the last column in the same order, and the first column goes to the first row reversed. Both and are bijections on the index set, so their composition is, and no cell is lost or duplicated.
Complexity
| Operation | Time | Extra space |
|---|---|---|
| any full traversal (row, column, diagonal, spiral, zigzag) | beyond output | |
| transpose / rotate / reflect in place (square) | ||
| rotate non-square | ||
| set matrix zeroes | ||
| staircase search | ||
| flat binary search | ||
| flood fill / islands | worst case for the stack or queue (a serpentine region), plus for a visited array unless the input may be marked in place | |
| BFS shortest path, multi-source BFS | for distances and queue | |
| game of life in place | per generation | |
| dense matrix multiply | output |
The constant factors are dominated by memory access order. A row-major scan of an array of 4-byte integers touches cache lines sequentially and runs at memory bandwidth; a column-major scan touches a new line almost every access once . DFS and BFS over a grid have poor locality by nature — the frontier jumps around — but the visited array and the grid itself are small enough to live in cache for grids up to a few million cells. Recursion in Python costs roughly a microsecond per call and the default recursion limit is 1000, so recursive DFS on anything bigger than a 30×30 grid risks a RecursionError on a serpentine region; use an explicit stack.
Implementation
Four canonical routines per language — spiral order, in-place 90° rotation, number of islands with iterative DFS, and the 01-matrix multi-source BFS — with the same tests as the trace tables.
from collections import deque
DIRS4 = ((1, 0), (-1, 0), (0, 1), (0, -1))
def spiral_order(grid: list[list[int]]) -> list[int]:
if not grid or not grid[0]:
return []
top, bottom, left, right = 0, len(grid) - 1, 0, len(grid[0]) - 1
out: list[int] = []
while top <= bottom and left <= right:
for c in range(left, right + 1):
out.append(grid[top][c])
top += 1
for r in range(top, bottom + 1):
out.append(grid[r][right])
right -= 1
if top <= bottom: # early-exit check 1
for c in range(right, left - 1, -1):
out.append(grid[bottom][c])
bottom -= 1
if left <= right: # early-exit check 2
for r in range(bottom, top - 1, -1):
out.append(grid[r][left])
left += 1
return out
def rotate_clockwise(a: list[list[int]]) -> None:
"""In place: transpose, then reverse each row. (r, c) -> (c, n-1-r)."""
n = len(a)
for r in range(n):
for c in range(r + 1, n):
a[r][c], a[c][r] = a[c][r], a[r][c]
for row in a:
row.reverse()
def num_islands(grid: list[list[str]]) -> int:
"""Counts 4-connected components of '1'. Mutates grid (sinks visited land)."""
if not grid:
return 0
n, m = len(grid), len(grid[0])
count = 0
for r0 in range(n):
for c0 in range(m):
if grid[r0][c0] != "1":
continue
count += 1
stack = [(r0, c0)]
grid[r0][c0] = "0" # mark when pushed
while stack:
r, c = stack.pop()
for dr, dc in DIRS4:
nr, nc = r + dr, c + dc
if 0 <= nr < n and 0 <= nc < m and grid[nr][nc] == "1":
grid[nr][nc] = "0"
stack.append((nr, nc))
return count
def zero_one_matrix(mat: list[list[int]]) -> list[list[int]]:
"""Distance from every cell to the nearest 0, by multi-source BFS."""
n, m = len(mat), len(mat[0])
dist = [[-1] * m for _ in range(n)]
q: deque[tuple[int, int]] = deque()
for r in range(n):
for c in range(m):
if mat[r][c] == 0:
dist[r][c] = 0
q.append((r, c))
while q:
r, c = q.popleft()
for dr, dc in DIRS4:
nr, nc = r + dr, c + dc
if 0 <= nr < n and 0 <= nc < m and dist[nr][nc] == -1:
dist[nr][nc] = dist[r][c] + 1
q.append((nr, nc))
return dist
if __name__ == "__main__":
assert spiral_order([[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12]]) == [1, 2, 3, 4, 8, 12, 11, 10, 9, 5, 6, 7]
assert spiral_order([[1, 2, 3], [4, 5, 6], [7, 8, 9]]) == [1, 2, 3, 6, 9, 8, 7, 4, 5]
assert spiral_order([[1], [2], [3]]) == [1, 2, 3]
assert spiral_order([]) == []
a = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
rotate_clockwise(a)
assert a == [[7, 4, 1], [8, 5, 2], [9, 6, 3]]
b = [[1, 2], [3, 4]]
rotate_clockwise(b)
assert b == [[3, 1], [4, 2]]
g = [list(row) for row in ["11000", "11000", "00100", "00011"]]
assert num_islands(g) == 3
g2 = [list(row) for row in ["11110", "11010", "11000", "00000"]]
assert num_islands(g2) == 1
assert zero_one_matrix([[0, 1, 1], [1, 1, 1], [1, 1, 0]]) == [[0, 1, 2], [1, 2, 1], [2, 1, 0]]
assert zero_one_matrix([[0, 0, 0], [0, 1, 0], [1, 1, 1]]) == [[0, 0, 0], [0, 1, 0], [1, 2, 1]]
print("matrices & grids: all tests passed")
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Deque;
import java.util.List;
public class MatricesAndGrids {
static final int[][] DIRS4 = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
static List<Integer> spiralOrder(int[][] grid) {
List<Integer> out = new ArrayList<>();
if (grid.length == 0 || grid[0].length == 0) return out;
int top = 0, bottom = grid.length - 1, left = 0, right = grid[0].length - 1;
while (top <= bottom && left <= right) {
for (int c = left; c <= right; c++) out.add(grid[top][c]);
top++;
for (int r = top; r <= bottom; r++) out.add(grid[r][right]);
right--;
if (top <= bottom) { // early-exit check 1
for (int c = right; c >= left; c--) out.add(grid[bottom][c]);
bottom--;
}
if (left <= right) { // early-exit check 2
for (int r = bottom; r >= top; r--) out.add(grid[r][left]);
left++;
}
}
return out;
}
/** In place: transpose, then reverse each row. (r, c) -> (c, n-1-r). */
static void rotateClockwise(int[][] a) {
int n = a.length;
for (int r = 0; r < n; r++) {
for (int c = r + 1; c < n; c++) {
int t = a[r][c]; a[r][c] = a[c][r]; a[c][r] = t;
}
}
for (int[] row : a) {
for (int i = 0, j = n - 1; i < j; i++, j--) {
int t = row[i]; row[i] = row[j]; row[j] = t;
}
}
}
/** Counts 4-connected components of '1'. Mutates grid (sinks visited land). */
static int numIslands(char[][] grid) {
if (grid.length == 0) return 0;
int n = grid.length, m = grid[0].length, count = 0;
Deque<int[]> stack = new ArrayDeque<>();
for (int r0 = 0; r0 < n; r0++) {
for (int c0 = 0; c0 < m; c0++) {
if (grid[r0][c0] != '1') continue;
count++;
grid[r0][c0] = '0'; // mark when pushed
stack.push(new int[]{r0, c0});
while (!stack.isEmpty()) {
int[] cell = stack.pop();
for (int[] d : DIRS4) {
int nr = cell[0] + d[0], nc = cell[1] + d[1];
if (nr >= 0 && nr < n && nc >= 0 && nc < m && grid[nr][nc] == '1') {
grid[nr][nc] = '0';
stack.push(new int[]{nr, nc});
}
}
}
}
}
return count;
}
/** Distance from every cell to the nearest 0, by multi-source BFS. */
static int[][] zeroOneMatrix(int[][] mat) {
int n = mat.length, m = mat[0].length;
int[][] dist = new int[n][m];
for (int[] row : dist) Arrays.fill(row, -1);
Deque<int[]> q = new ArrayDeque<>();
for (int r = 0; r < n; r++) {
for (int c = 0; c < m; c++) {
if (mat[r][c] == 0) { dist[r][c] = 0; q.add(new int[]{r, c}); }
}
}
while (!q.isEmpty()) {
int[] cell = q.poll();
for (int[] d : DIRS4) {
int nr = cell[0] + d[0], nc = cell[1] + d[1];
if (nr >= 0 && nr < n && nc >= 0 && nc < m && dist[nr][nc] == -1) {
dist[nr][nc] = dist[cell[0]][cell[1]] + 1;
q.add(new int[]{nr, nc});
}
}
}
return dist;
}
static char[][] toGrid(String... rows) {
char[][] g = new char[rows.length][];
for (int i = 0; i < rows.length; i++) g[i] = rows[i].toCharArray();
return g;
}
static void check(boolean ok, String what) {
if (!ok) throw new AssertionError(what);
}
public static void main(String[] args) {
check(spiralOrder(new int[][]{{1, 2, 3, 4}, {5, 6, 7, 8}, {9, 10, 11, 12}})
.equals(List.of(1, 2, 3, 4, 8, 12, 11, 10, 9, 5, 6, 7)), "spiral 3x4");
check(spiralOrder(new int[][]{{1, 2, 3}, {4, 5, 6}, {7, 8, 9}})
.equals(List.of(1, 2, 3, 6, 9, 8, 7, 4, 5)), "spiral 3x3");
check(spiralOrder(new int[][]{{1}, {2}, {3}}).equals(List.of(1, 2, 3)), "spiral column");
check(spiralOrder(new int[0][0]).isEmpty(), "spiral empty");
int[][] a = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};
rotateClockwise(a);
check(Arrays.deepEquals(a, new int[][]{{7, 4, 1}, {8, 5, 2}, {9, 6, 3}}), "rotate 3x3");
int[][] b = {{1, 2}, {3, 4}};
rotateClockwise(b);
check(Arrays.deepEquals(b, new int[][]{{3, 1}, {4, 2}}), "rotate 2x2");
check(numIslands(toGrid("11000", "11000", "00100", "00011")) == 3, "islands = 3");
check(numIslands(toGrid("11110", "11010", "11000", "00000")) == 1, "islands = 1");
check(Arrays.deepEquals(zeroOneMatrix(new int[][]{{0, 1, 1}, {1, 1, 1}, {1, 1, 0}}),
new int[][]{{0, 1, 2}, {1, 2, 1}, {2, 1, 0}}), "01 matrix a");
check(Arrays.deepEquals(zeroOneMatrix(new int[][]{{0, 0, 0}, {0, 1, 0}, {1, 1, 1}}),
new int[][]{{0, 0, 0}, {0, 1, 0}, {1, 2, 1}}), "01 matrix b");
System.out.println("matrices & grids: all tests passed");
}
}
#include <algorithm>
#include <cassert>
#include <deque>
#include <iostream>
#include <string>
#include <utility>
#include <vector>
using std::vector;
static const int DIRS4[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
vector<int> spiralOrder(const vector<vector<int>>& grid) {
vector<int> out;
if (grid.empty() || grid[0].empty()) return out;
int top = 0, bottom = (int)grid.size() - 1, left = 0, right = (int)grid[0].size() - 1;
while (top <= bottom && left <= right) {
for (int c = left; c <= right; ++c) out.push_back(grid[top][c]);
++top;
for (int r = top; r <= bottom; ++r) out.push_back(grid[r][right]);
--right;
if (top <= bottom) { // early-exit check 1
for (int c = right; c >= left; --c) out.push_back(grid[bottom][c]);
--bottom;
}
if (left <= right) { // early-exit check 2
for (int r = bottom; r >= top; --r) out.push_back(grid[r][left]);
++left;
}
}
return out;
}
// In place: transpose, then reverse each row. (r, c) -> (c, n-1-r).
void rotateClockwise(vector<vector<int>>& a) {
int n = (int)a.size();
for (int r = 0; r < n; ++r)
for (int c = r + 1; c < n; ++c)
std::swap(a[r][c], a[c][r]);
for (auto& row : a) std::reverse(row.begin(), row.end());
}
// Counts 4-connected components of '1'. Mutates grid (sinks visited land).
int numIslands(vector<std::string>& grid) {
if (grid.empty()) return 0;
int n = (int)grid.size(), m = (int)grid[0].size(), count = 0;
vector<std::pair<int, int>> stack;
for (int r0 = 0; r0 < n; ++r0) {
for (int c0 = 0; c0 < m; ++c0) {
if (grid[r0][c0] != '1') continue;
++count;
grid[r0][c0] = '0'; // mark when pushed
stack.push_back({r0, c0});
while (!stack.empty()) {
auto [r, c] = stack.back();
stack.pop_back();
for (const auto& d : DIRS4) {
int nr = r + d[0], nc = c + d[1];
if (nr >= 0 && nr < n && nc >= 0 && nc < m && grid[nr][nc] == '1') {
grid[nr][nc] = '0';
stack.push_back({nr, nc});
}
}
}
}
}
return count;
}
// Distance from every cell to the nearest 0, by multi-source BFS.
vector<vector<int>> zeroOneMatrix(const vector<vector<int>>& mat) {
int n = (int)mat.size(), m = (int)mat[0].size();
vector<vector<int>> dist(n, vector<int>(m, -1));
std::deque<std::pair<int, int>> q;
for (int r = 0; r < n; ++r)
for (int c = 0; c < m; ++c)
if (mat[r][c] == 0) { dist[r][c] = 0; q.push_back({r, c}); }
while (!q.empty()) {
auto [r, c] = q.front();
q.pop_front();
for (const auto& d : DIRS4) {
int nr = r + d[0], nc = c + d[1];
if (nr >= 0 && nr < n && nc >= 0 && nc < m && dist[nr][nc] == -1) {
dist[nr][nc] = dist[r][c] + 1;
q.push_back({nr, nc});
}
}
}
return dist;
}
int main() {
assert((spiralOrder({{1, 2, 3, 4}, {5, 6, 7, 8}, {9, 10, 11, 12}}) == vector<int>{1, 2, 3, 4, 8, 12, 11, 10, 9, 5, 6, 7}));
assert((spiralOrder({{1, 2, 3}, {4, 5, 6}, {7, 8, 9}}) == vector<int>{1, 2, 3, 6, 9, 8, 7, 4, 5}));
assert((spiralOrder({{1}, {2}, {3}}) == vector<int>{1, 2, 3}));
assert(spiralOrder({}).empty());
vector<vector<int>> a = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};
rotateClockwise(a);
assert((a == vector<vector<int>>{{7, 4, 1}, {8, 5, 2}, {9, 6, 3}}));
vector<vector<int>> b = {{1, 2}, {3, 4}};
rotateClockwise(b);
assert((b == vector<vector<int>>{{3, 1}, {4, 2}}));
vector<std::string> g = {"11000", "11000", "00100", "00011"};
assert(numIslands(g) == 3);
vector<std::string> g2 = {"11110", "11010", "11000", "00000"};
assert(numIslands(g2) == 1);
assert((zeroOneMatrix({{0, 1, 1}, {1, 1, 1}, {1, 1, 0}}) == vector<vector<int>>{{0, 1, 2}, {1, 2, 1}, {2, 1, 0}}));
assert((zeroOneMatrix({{0, 0, 0}, {0, 1, 0}, {1, 1, 1}}) == vector<vector<int>>{{0, 0, 0}, {0, 1, 0}, {1, 2, 1}}));
std::cout << "matrices & grids: all tests passed\n";
return 0;
}
const DIRS4: [number, number][] = [[1, 0], [-1, 0], [0, 1], [0, -1]];
function spiralOrder(grid: number[][]): number[] {
const out: number[] = [];
if (grid.length === 0 || grid[0].length === 0) return out;
let top = 0, bottom = grid.length - 1, left = 0, right = grid[0].length - 1;
while (top <= bottom && left <= right) {
for (let c = left; c <= right; c++) out.push(grid[top][c]);
top++;
for (let r = top; r <= bottom; r++) out.push(grid[r][right]);
right--;
if (top <= bottom) { // early-exit check 1
for (let c = right; c >= left; c--) out.push(grid[bottom][c]);
bottom--;
}
if (left <= right) { // early-exit check 2
for (let r = bottom; r >= top; r--) out.push(grid[r][left]);
left++;
}
}
return out;
}
// In place: transpose, then reverse each row. (r, c) -> (c, n-1-r).
function rotateClockwise(a: number[][]): void {
const n = a.length;
for (let r = 0; r < n; r++) {
for (let c = r + 1; c < n; c++) {
const t = a[r][c]; a[r][c] = a[c][r]; a[c][r] = t;
}
}
for (const row of a) row.reverse();
}
// Counts 4-connected components of "1". Mutates grid (sinks visited land).
function numIslands(grid: string[][]): number {
if (grid.length === 0) return 0;
const n = grid.length, m = grid[0].length;
let count = 0;
for (let r0 = 0; r0 < n; r0++) {
for (let c0 = 0; c0 < m; c0++) {
if (grid[r0][c0] !== "1") continue;
count++;
grid[r0][c0] = "0"; // mark when pushed
const stack: [number, number][] = [[r0, c0]];
while (stack.length > 0) {
const [r, c] = stack.pop()!;
for (const [dr, dc] of DIRS4) {
const nr = r + dr, nc = c + dc;
if (nr >= 0 && nr < n && nc >= 0 && nc < m && grid[nr][nc] === "1") {
grid[nr][nc] = "0";
stack.push([nr, nc]);
}
}
}
}
}
return count;
}
// Distance from every cell to the nearest 0, by multi-source BFS.
function zeroOneMatrix(mat: number[][]): number[][] {
const n = mat.length, m = mat[0].length;
const dist: number[][] = Array.from({ length: n }, () => new Array(m).fill(-1));
const queue: [number, number][] = [];
let head = 0; // index-based queue: O(1) dequeue
for (let r = 0; r < n; r++) {
for (let c = 0; c < m; c++) {
if (mat[r][c] === 0) { dist[r][c] = 0; queue.push([r, c]); }
}
}
while (head < queue.length) {
const [r, c] = queue[head++];
for (const [dr, dc] of DIRS4) {
const nr = r + dr, nc = c + dc;
if (nr >= 0 && nr < n && nc >= 0 && nc < m && dist[nr][nc] === -1) {
dist[nr][nc] = dist[r][c] + 1;
queue.push([nr, nc]);
}
}
}
return dist;
}
function check(ok: boolean, what: string): void {
if (!ok) throw new Error("FAILED: " + what);
}
const eq = (a: unknown, b: unknown): boolean => JSON.stringify(a) === JSON.stringify(b);
const toGrid = (rows: string[]): string[][] => rows.map(r => r.split(""));
check(eq(spiralOrder([[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12]]), [1, 2, 3, 4, 8, 12, 11, 10, 9, 5, 6, 7]), "spiral 3x4");
check(eq(spiralOrder([[1, 2, 3], [4, 5, 6], [7, 8, 9]]), [1, 2, 3, 6, 9, 8, 7, 4, 5]), "spiral 3x3");
check(eq(spiralOrder([[1], [2], [3]]), [1, 2, 3]), "spiral column");
check(eq(spiralOrder([]), []), "spiral empty");
const a = [[1, 2, 3], [4, 5, 6], [7, 8, 9]];
rotateClockwise(a);
check(eq(a, [[7, 4, 1], [8, 5, 2], [9, 6, 3]]), "rotate 3x3");
const b = [[1, 2], [3, 4]];
rotateClockwise(b);
check(eq(b, [[3, 1], [4, 2]]), "rotate 2x2");
check(numIslands(toGrid(["11000", "11000", "00100", "00011"])) === 3, "islands = 3");
check(numIslands(toGrid(["11110", "11010", "11000", "00000"])) === 1, "islands = 1");
check(eq(zeroOneMatrix([[0, 1, 1], [1, 1, 1], [1, 1, 0]]), [[0, 1, 2], [1, 2, 1], [2, 1, 0]]), "01 matrix a");
check(eq(zeroOneMatrix([[0, 0, 0], [0, 1, 0], [1, 1, 1]]), [[0, 0, 0], [0, 1, 0], [1, 2, 1]]), "01 matrix b");
console.log("matrices & grids: all tests passed");
Two implementation notes. In TypeScript, Array.prototype.shift() is in most engines for large arrays, so a BFS queue built on shift() degrades to ; the index-based queue above (a head pointer into a growing array) keeps dequeue at . In Java, ArrayDeque is the right queue; LinkedList works but allocates a node per element and is noticeably slower. Both points are developed in Queues, Deques & Circular Buffers.
Variant: layer-by-layer rotation and the staircase search
def rotate_by_layers(a: list[list[int]]) -> None:
"""In place 90° clockwise, moving each element exactly once."""
n = len(a)
for layer in range(n // 2):
first, last = layer, n - 1 - layer
for i in range(first, last):
off = i - first
top = a[first][i]
a[first][i] = a[last - off][first] # left -> top
a[last - off][first] = a[last][last - off] # bottom -> left
a[last][last - off] = a[i][last] # right -> bottom
a[i][last] = top # top -> right
def staircase_search(m: list[list[int]], target: int) -> tuple[bool, int]:
"""Rows and columns sorted ascending. Returns (found, steps)."""
r, c, steps = 0, len(m[0]) - 1, 0
while r < len(m) and c >= 0:
steps += 1
if m[r][c] == target:
return True, steps
if m[r][c] > target:
c -= 1 # whole column eliminated
else:
r += 1 # whole row eliminated
return False, steps
a = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
rotate_by_layers(a)
assert a == [[7, 4, 1], [8, 5, 2], [9, 6, 3]]
b = [[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12], [13, 14, 15, 16]]
rotate_by_layers(b)
assert b == [[13, 9, 5, 1], [14, 10, 6, 2], [15, 11, 7, 3], [16, 12, 8, 4]]
M = [[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]]
assert staircase_search(M, 5) == (True, 5)
assert staircase_search(M, 20) == (False, 9)
print("rotation by layers and staircase search ok")
Real-world uses
Images are grids. A greyscale image is an matrix of intensities; colour images add a channel dimension. A convolution kernel (blur, sharpen, edge detection) is a small matrix slid over every pixel — the stencil pattern — and the boundary handling you learn on interview grids (clamp, wrap, or skip) is exactly what image libraries call padding modes. The paint-bucket tool is flood fill with a tolerance on the colour difference; GIMP and Photoshop implement it as an iterative scan-line fill to avoid recursion. Connected-component labelling (number of islands on a binary image) is the first step of blob detection in OCR and industrial inspection; OpenCV's connectedComponents implements it with a two-pass Union-Find algorithm, not DFS, for cache friendliness.
Game maps and pathfinding. Tile-based games store the world as a grid; movement is a BFS or A* over passable tiles; "fog of war" and "influence maps" are multi-source BFS from units. Roguelikes use flood fill from the player to decide which tiles are reachable. The Graphs lesson covers Dijkstra and A* for weighted terrain.
Spreadsheets. A sheet is a sparse grid — most of the Excel cells are empty — stored as a dictionary of keys or a compressed structure keyed by row. The dependency graph between formulas is the implicit graph; recalculation is a topological sort, and the "circular reference" error is cycle detection.
GIS rasters. Elevation models, land-cover maps and satellite imagery are grids with georeferencing; watershed delineation is flood fill on the elevation raster, viewshed analysis is a ray sweep, and raster tiles are chunked for the spatial indexes described in Spatial Indexing.
Cache-friendly traversal. Dense numerical kernels — matrix multiply, stencils, image filters — are memory-bound, and the difference between walking memory sequentially and striding across rows is the difference between hitting DRAM bandwidth and waiting on cache misses. Loop interchange, tiling (processing the grid in cache-sized blocks) and the row-major rule are the first optimisations any performance engineer applies; see How Data Structures Live in Memory.
Dense linear algebra. BLAS (Basic Linear Algebra Subprograms) has defined the interface for vector and matrix operations since 1979; optimised implementations (OpenBLAS, Intel MKL, Apple Accelerate, cuBLAS) deliver near-peak hardware throughput for GEMM. BLAS and LAPACK are Fortran-heritage and column-major; NumPy defaults to row-major (C order) and silently passes transposition flags to BLAS when it calls it. Reading ndarray.strides tells you how many bytes to step for each index, which makes the layout concrete: a C-order float64 array of shape (3, 4) has strides (32, 8).
Cellular automata and simulation. Game of Life, forest-fire models, lattice fluid simulations and finite-difference PDE solvers all update a grid from its neighbours — double buffering at scale, bit-packing for small instances. Hashlife uses memoisation on quadtrees to simulate Life patterns for astronomically many generations.
Pitfalls & edge cases
Rows and columns swapped. grid[c][r] compiles, runs, and is wrong only on non-square inputs. Test every grid routine on a non-square matrix (3×4, never 3×3 only). Name variables r/c or row/col, never x/y or i/j when both appear.
Visited handling. Mark cells as visited when you enqueue/push them, not when you dequeue. Marking on dequeue allows the same cell to be enqueued from several neighbours, which is a correctness problem for counting (double-counts) and a performance problem for BFS (queue size blows up).
Mutating the input as the visited marker. Convenient, but it destroys the caller's data. Ask. If the grid is const, immutable (strings in most languages), or needed later, allocate a boolean grid or a set of flattened indices.
Recursion depth. A grid with one serpentine island is a recursion depth of . Python dies at 1000 frames by default; Java's default thread stack (typically 512 KB–1 MB) manages on the order of frames. Use an explicit stack for anything beyond toy sizes. In contests you may raise sys.setrecursionlimit and run in a thread with a bigger stack; in production, never.
Diagonals. Decide whether connectivity is 4- or 8-neighbour from the problem statement; "islands" is 4-connected on LeetCode, "number of regions in a binary image" is often 8-connected. Using the wrong one changes the answer silently.
Empty grid and single row/column. grid = [], grid = [[]], grid = [[1]], a row and an column are the inputs that break spiral traversal and bounds checks. Test all of them.
Non-square rotation. rotates into ; in-place code written for square matrices will index out of bounds or corrupt data. Check n == m or allocate.
Game of life boundary. Cells on the edge have fewer neighbours; count only in-bounds ones. Some variants (torus) wrap instead — read the statement.
Shift-based queues. Array.shift() in JavaScript and list.pop(0) in Python are . Use collections.deque in Python and an index pointer or a linked deque in JavaScript.
Integer division for flattening. idx // m and idx % m with the number of columns , not rows. Flattening with the wrong dimension is the 1D version of the row/column swap.
Overflow in matrix multiplication. Products of two int matrices overflow 32 bits trivially (two entries of ). Accumulate in 64-bit or modulo a prime.
Variations
Torus (wraparound) grids. Neighbours use (r + dr) % n and (c + dc) % m with the non-negative modulo fix for negative offsets ((r + dr + n) % n). Pac-Man and many cellular automata do this; the graph is now regular with every vertex of degree 4.
Hex grids. Hexagonal cells have six neighbours and no simple offsets that work for every row. The clean approach is axial coordinates with six fixed neighbour offsets (+1,0), (-1,0), (0,+1), (0,-1), (+1,-1), (-1,+1), and the hex distance is . Red Blob Games' Hexagonal Grids guide is the standard reference.
3D grids. Voxels, with 6-neighbour (face) or 26-neighbour connectivity. Flattening is x * (m * k) + y * k + z. Everything on this page carries over with one more loop; BFS over a voxel grid is a million vertices, still fine.
Knight moves and other move sets. A knight on a chessboard is a grid graph with eight offsets (±1, ±2), (±2, ±1); "minimum knight moves" is BFS. Any fixed move set is just a different direction array.
Weighted grids. Cost to enter a cell → Dijkstra ( with a heap). Costs restricted to 0 and 1 (e.g. "minimum walls to break") → 0-1 BFS with a deque in . Costs that are "turns" or "direction changes" → add the direction to the state, making the graph vertices.
State-augmented grids. Problems like "shortest path with at most obstacle eliminations" (LeetCode 1293) make the vertex , multiplying the graph by . The BFS is unchanged; only the visited set grows.
Grid DP. When moves are restricted to right/down (a DAG), counting and optimisation become dynamic programming with a row-major fill — the Grid & Path DP lesson in the dynamic-programming module.
Practice ladder
Each problem is described in my own words; follow the link for the formal statement.
1. Spiral Matrix (LeetCode 54) — Emit all cells of an matrix in clockwise spiral order. Teaches the four-boundary loop and the two early-exit checks.
Hint
Keep top, bottom, left, right. After the top and right walks, guard the bottom and left walks with top <= bottom and left <= right.
2. Spiral Matrix II (LeetCode 59) — Fill an matrix with in spiral order. Same loop, writing instead of reading; teaches that generation and traversal are the same algorithm.
Hint
Run the spiral loop with a counter and assign grid[r][c] = counter at each visit.
3. Rotate Image (LeetCode 48) — Rotate a square matrix 90° clockwise in place. Teaches the transpose-then-reverse decomposition and its proof.
Hint
Transpose by swapping a[r][c] with a[c][r] for c > r, then reverse each row. Verify the corner mapping .
4. Set Matrix Zeroes (LeetCode 73) — Zero the entire row and column of every zero cell, in constant extra space. Teaches storing flags inside the matrix.
Hint
Use grid[0][c] and grid[r][0] as the column/row flags, with one extra boolean for the first column. Process the first row and column last.
Solution
def set_zeroes(mat: list[list[int]]) -> None:
n, m = len(mat), len(mat[0])
first_col_zero = any(mat[r][0] == 0 for r in range(n))
for r in range(n):
for c in range(1, m):
if mat[r][c] == 0:
mat[r][0] = 0 # row r flag
mat[0][c] = 0 # column c flag
for r in range(1, n):
for c in range(1, m):
if mat[r][0] == 0 or mat[0][c] == 0:
mat[r][c] = 0
if mat[0][0] == 0: # first row flag lives here
for c in range(m):
mat[0][c] = 0
if first_col_zero:
for r in range(n):
mat[r][0] = 0
a = [[1, 1, 1], [1, 0, 1], [1, 1, 1]]
set_zeroes(a)
assert a == [[1, 0, 1], [0, 0, 0], [1, 0, 1]]
b = [[0, 1, 2, 0], [3, 4, 5, 2], [1, 3, 1, 5]]
set_zeroes(b)
assert b == [[0, 0, 0, 0], [0, 4, 5, 0], [0, 3, 1, 0]]
print("73 ok")
time, extra space. The first row and column are overwritten last because they carry the flags everyone else reads.
5. Search a 2D Matrix (LeetCode 74) — Rows sorted and each row's first element exceeds the previous row's last. Teaches treating the matrix as a flat sorted array with divmod.
Hint
Binary search over idx in [0, n*m), reading mat[idx // m][idx % m].
6. Search a 2D Matrix II (LeetCode 240) — Rows and columns independently sorted. Teaches the staircase search and why the top-left corner is the wrong start.
Hint
Start at the top-right. Greater than target → move left (column eliminated). Less → move down (row eliminated). At most steps.
Solution
def search_matrix(mat: list[list[int]], target: int) -> bool:
if not mat or not mat[0]:
return False
r, c = 0, len(mat[0]) - 1
while r < len(mat) and c >= 0:
v = mat[r][c]
if v == target:
return True
if v > target:
c -= 1
else:
r += 1
return False
M = [[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]]
assert search_matrix(M, 5) is True
assert search_matrix(M, 20) is False
assert search_matrix([[-5]], -5) is True
print("240 ok")
time, space. Each comparison discards a whole row or column, as the Correctness section proves.
7. Flood Fill (LeetCode 733) — Recolour the 4-connected region containing a seed pixel. Teaches the basic fill and the "new colour equals old colour" infinite-loop guard.
Hint
Return immediately if the new colour equals the seed's colour. Otherwise DFS/BFS from the seed over cells with the original colour.
8. Number of Islands (LeetCode 200) — Count 4-connected groups of land cells. Teaches scan-and-sink.
Hint
Scan every cell; on unvisited land, increment and flood-fill the island to water. Use an explicit stack for large grids.
9. Counting Rooms (CSES 1192) — Count connected floor regions in a map up to . Teaches islands at a scale where recursion fails.
Hint
Identical to Number of Islands on a -cell grid: iterative DFS or BFS, and fast input reading.
10. Rotting Oranges (LeetCode 994) — Rotten oranges spread to adjacent fresh ones every minute; find when all are rotten, or report impossible. Teaches multi-source BFS with level counting and a final reachability check.
Hint
Enqueue every rotten orange at time 0. BFS level by level; the answer is the number of levels that rotted at least one orange. If a fresh orange remains, return −1.
Solution
from collections import deque
def oranges_rotting(grid: list[list[int]]) -> int:
n, m = len(grid), len(grid[0])
q = deque()
fresh = 0
for r in range(n):
for c in range(m):
if grid[r][c] == 2:
q.append((r, c))
elif grid[r][c] == 1:
fresh += 1
minutes = 0
while q and fresh:
for _ in range(len(q)): # one level = one minute
r, c = q.popleft()
for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
nr, nc = r + dr, c + dc
if 0 <= nr < n and 0 <= nc < m and grid[nr][nc] == 1:
grid[nr][nc] = 2
fresh -= 1
q.append((nr, nc))
minutes += 1
return minutes if fresh == 0 else -1
assert oranges_rotting([[2, 1, 1], [1, 1, 0], [0, 1, 1]]) == 4
assert oranges_rotting([[2, 1, 1], [0, 1, 1], [1, 0, 1]]) == -1
assert oranges_rotting([[0, 2]]) == 0
print("994 ok")
time and space. Looping while q and fresh stops as soon as nothing is left to rot, so an all-rotten grid reports 0 rather than 1.
11. 01 Matrix (LeetCode 542) — For each cell, the distance to the nearest 0. Teaches multi-source BFS as a distance transform.
Hint
Put all zeros in the queue with distance 0; BFS outward. This is the canonical implementation above.
12. Shortest Path in Binary Matrix (LeetCode 1091) — Shortest 8-directional path from the top-left to the bottom-right through open cells. Teaches single-source BFS with 8 directions and path length counted in cells.
Hint
BFS from with DIRS8, marking visited on enqueue. The start counts as 1. Return −1 if the start or end is blocked or the end is unreachable.
Solution
from collections import deque
def shortest_path_binary_matrix(grid: list[list[int]]) -> int:
n = len(grid)
if grid[0][0] or grid[n - 1][n - 1]:
return -1
dirs = [(dr, dc) for dr in (-1, 0, 1) for dc in (-1, 0, 1) if (dr, dc) != (0, 0)]
dist = [[0] * n for _ in range(n)]
dist[0][0] = 1
q = deque([(0, 0)])
while q:
r, c = q.popleft()
if (r, c) == (n - 1, n - 1):
return dist[r][c]
for dr, dc in dirs:
nr, nc = r + dr, c + dc
if 0 <= nr < n and 0 <= nc < n and grid[nr][nc] == 0 and dist[nr][nc] == 0:
dist[nr][nc] = dist[r][c] + 1
q.append((nr, nc))
return -1
assert shortest_path_binary_matrix([[0, 1], [1, 0]]) == 2
assert shortest_path_binary_matrix([[0, 0, 0], [1, 1, 0], [1, 1, 0]]) == 4
assert shortest_path_binary_matrix([[1, 0, 0], [1, 1, 0], [1, 1, 0]]) == -1
print("1091 ok")
time and space. The dist array doubles as the visited set (0 = unvisited), which works because the start is assigned 1.
13. Labyrinth (CSES 1193) — Find a path from A to B in a wall grid and print the move sequence. Teaches BFS with parent pointers for path reconstruction.
Hint
BFS from A; store for each cell the direction you arrived from. Walk back from B to A and reverse the letters.
14. Game of Life (LeetCode 289) — Compute the next generation of Conway's Life in place. Teaches two-bit state encoding for simultaneous updates.
Hint
Count live neighbours using cell & 1. Set bit 1 for cells alive next generation. Finally shift every cell right by one.
Solution
def game_of_life(board: list[list[int]]) -> None:
n, m = len(board), len(board[0])
for r in range(n):
for c in range(m):
live = 0
for dr in (-1, 0, 1):
for dc in (-1, 0, 1):
if dr == 0 and dc == 0:
continue
nr, nc = r + dr, c + dc
if 0 <= nr < n and 0 <= nc < m:
live += board[nr][nc] & 1 # read ONLY the old bit
if (board[r][c] & 1 and live in (2, 3)) or (board[r][c] & 1 == 0 and live == 3):
board[r][c] |= 2 # write the new bit
for r in range(n):
for c in range(m):
board[r][c] >>= 1
b = [[0, 1, 0], [0, 0, 1], [1, 1, 1], [0, 0, 0]]
game_of_life(b)
assert b == [[0, 0, 0], [1, 0, 1], [0, 1, 1], [0, 1, 0]]
b2 = [[1, 1], [1, 0]]
game_of_life(b2)
assert b2 == [[1, 1], [1, 1]]
print("289 ok")
time, extra space. Bit 0 is never modified during the first pass, so every neighbour count sees the original board.
15. Spiral Matrix III (LeetCode 885) — Walk an outward spiral from a start cell, recording in-bounds cells, until all are visited. Teaches spirals with growing step lengths and out-of-bounds tolerance.
Hint
Step lengths go 1, 1, 2, 2, 3, 3, …; turn right after each run; record only in-bounds cells; stop after records.
Common mistakes & interview follow-ups
"The grid is — what changes?" You cannot allocate cells. Ask what is actually populated: if only cells matter, compress coordinates to a (or smaller) grid, or store the grid sparsely in a hash map and let BFS discover cells lazily.
"What if the grid does not fit in memory at all?" Process it in tiles that do, with a one-row/one-column halo so neighbours across tile borders are available; connected components across tiles are merged with Union-Find on the border labels. This is how satellite imagery and large microscopy scans are processed.
"Can you find the shortest path faster than BFS?" For unit weights BFS is already linear, which is optimal in the worst case. With a known target, A* with the Manhattan heuristic explores fewer cells on typical maps but has the same worst case. Bidirectional BFS halves the explored radius.
"What if moving into a cell has a cost?" Dijkstra. If costs are 0 or 1, 0-1 BFS with a deque stays linear.
"Why not recursion for flood fill?" Stack depth equals region path length — up to . Use an explicit stack or BFS; mention scan-line fill as what paint programs do.
"Can rotation be done for a non-square matrix in place?" No: the shape changes. In-place transposition of a non-square matrix is possible via cycle-following on the flat array, but is intricate; allocate.
"How would you parallelise number of islands?" Split into tiles, label components within each tile independently, then unite labels across tile boundaries with Union-Find — the two-pass connected-component labelling algorithm used in OpenCV.
"Game of Life on an infinite grid?" Store only live cells in a hash set; the next generation's candidates are live cells and their neighbours. Hashlife goes further with quadtree memoisation.
"The matrix is read-only — number of islands without mutating?" Allocate an boolean visited array, or a set of flattened indices r * m + c. Same complexity, extra memory.
Common mistakes interviewers watch for: grid[c][r]; marking visited on dequeue; recursive DFS on a big grid; forgetting the spiral guards (double-emitting the middle row); starting staircase search from the top-left; shift() queues in JavaScript; using [[0]*m]*n in Python.
Quick quiz
1. In spiral order, why are the third and fourth walks guarded but the first two are not?
Answer
The loop condition top <= bottom and left <= right already guarantees the first two walks are over a non-empty row and column. After the top walk moves top down and the right walk moves right left, the remaining rectangle may have become a single row or column that has just been consumed; the guards prevent walking it again in reverse.
2. Give the index mapping for a 90° clockwise rotation of an matrix and the two in-place operations that compose to it.
Answer
. Transpose () followed by reversing each row ().
3. Why does the staircase search start at the top-right corner rather than the top-left?
Answer
At the top-right, the value is the largest in its row and the smallest in its column, so comparing with the target eliminates either the row (move down) or the column (move left). At the top-left both neighbours are larger, so no comparison eliminates anything.
4. How does multi-source BFS compute "distance to the nearest source" in one pass, and why is it correct?
Answer
Enqueue all sources at distance 0 and run ordinary BFS. It is equivalent to BFS from an imaginary super-source adjacent to every real source; BFS discovers cells in nondecreasing distance order, so each cell's first discovery is via its nearest source.
5. You must flood-fill a grid in Python. What goes wrong with a recursive solution and what do you do instead?
Answer
A serpentine region can have path length up to , far past Python's default recursion limit of 1000, so you get a RecursionError. Use an explicit stack (iterative DFS) or a deque-based BFS.
Further reading / sources
- Cormen, Leiserson, Rivest, Stein, Introduction to Algorithms (CLRS), 4th ed., chapter 20 "Elementary Graph Algorithms" — BFS and its correctness proof, which grid BFS inherits; chapter 4 covers Strassen's algorithm.
- Steven Skiena, The Algorithm Design Manual, 3rd ed., chapter 7 "Graph Traversal" — flood fill and connected components as DFS/BFS applications.
- Robert Sedgewick and Kevin Wayne, Algorithms, 4th ed., section 4.1 — connected components and Union-Find.
- cp-algorithms: Breadth-first search, 0-1 BFS, Finding connected components.
- Amit Patel, Red Blob Games, Hexagonal Grids — the definitive practical reference for hex coordinates.
- Volker Strassen, "Gaussian elimination is not optimal", Numerische Mathematik 13 (1969) — the algorithm.
- Ulrich Drepper, What Every Programmer Should Know About Memory (2007) — why loop order on a matrix matters.
- NumPy documentation on array memory layout and strides.
Previous lesson: Prefix Sums & Difference Arrays · Next lesson: Strings in Depth
Related: Module 1 overview · Arrays & Strings · Graphs · Queues, Deques & Circular Buffers · Stacks · Backtracking & Recursion · Sorting & Searching · How Data Structures Live in Memory · Your Language's Data Structures · Course home