Matrix
Topic type: Data Structure | LeetCode problems: 250+
Core Concepts
Matrix — a 2D array of m rows and n columns; element at row r, column c is accessed as matrix[r][c] in O(1). The grid is the primary representation for 2D spatial problems.
Cell — a single position (r, c). Rows are indexed 0 to m−1; columns 0 to n−1.
In-bounds — a cell (r, c) is valid iff 0 ≤ r < m and 0 ≤ c < n. Every grid traversal gates on this check before accessing a neighbor.
4-directional adjacency — a cell's neighbors are up, down, left, right: (r-1,c), (r+1,c), (r,c-1), (r,c+1). The standard for "connected" in grid problems.
8-directional adjacency — adds the four diagonals. Used in game-of-life and chess-piece movement problems.
Diagonal — cells where r - c is constant (top-left → bottom-right). Anti-diagonal — cells where r + c is constant (top-right → bottom-left). Both are key for traversal and grouping.
Transpose — swap rows and columns: M[i][j] ↔ M[j][i]. Only defined in-place on a square matrix.
2D prefix sum — P[i][j] = sum of all elements in the rectangle (0,0) to (i-1, j-1). Range query over any rectangle is O(1) after O(mn) build.
Visited marker — a boolean visited array or in-place mutation tracking which cells have been processed; prevents cycles in BFS/DFS.
Structural Invariants
| Property | Guarantee | What breaks if violated |
|---|---|---|
| Row count m, col count n fixed | matrix[r][c] always valid for 0 ≤ r < m, 0 ≤ c < n | Index error on boundary cells |
| Square matrix (m == n) | In-place transpose and rotation are safe | Rotation formulas produce out-of-bounds writes |
| Sorted row matrix | Each row is non-decreasing; enables row binary search | Binary search yields wrong result |
| Sorted matrix (row + col) | matrix[r][c] ≤ matrix[r][c+1] and ≤ matrix[r+1][c] | Staircase search doesn't converge correctly |
| Binary matrix | Values ∈ {0, 1}; determines which cells are traversable | Connected-component logic mixes regions |
Internal Representation
List of lists (Python) — matrix[r][c]; default in interviews. Allocation trap: [[0]*n]*m makes all rows the same object — use [[0]*n for _ in range(m)].
Flattened 1D array — single array of length m*n; cell (r, c) maps to index r*n + c; reverse: r = idx // n, c = idx % n. Useful for Union-Find on grid problems (node id = flattened index).
Visited array — separate visited = [[False]*n for _ in range(m)]; or re-use the grid itself by writing a sentinel value (e.g., flip 1 → 0 or '#') to mark visited in-place, saving O(mn) space.
Sparse matrix — dict of (r,c) → value; for grids where most cells are zero or empty (coordinate-compressed or infinite grids).
2D prefix sum array — P of size (m+1) × (n+1) with P[0][*] = P[*][0] = 0; built in O(mn), answers rectangle sum queries in O(1).
Types / Variants
| Variant | Distinguishing property | When to prefer |
|---|---|---|
| Square matrix (m == n) | Rotation and transpose are in-place | Rotation, transpose, diagonal traversal |
| Binary matrix | Values ∈ {0, 1} | Island counting, 0-1 BFS, flood fill |
| Sorted rows matrix | Each row sorted; rows not globally sorted | Row binary search, search in O(m log n) |
| Sorted matrix | Sorted rows + columns; smallest at [0][0], largest at [m-1][n-1] | Staircase search in O(m+n) |
| Sparse grid | Most cells empty; effective grid is large but dense region is small | Coordinate compression, dict representation |
| Weighted grid | Each cell has a cost to enter/traverse | Dijkstra or 0-1 BFS for shortest path |
Traversals & Access Patterns
Row-by-row (raster scan) — nested loops for r in range(m): for c in range(n). The default; cache-friendly in row-major storage.
Column-by-column — outer loop over c, inner over r. Needed when problems process one column at a time (histogram problems, column-sorted data).
Diagonal traversal — group cells by r - c; iterate over each group. Index r - c ranges from -(n-1) to m-1.
Anti-diagonal traversal — group cells by r + c; index ranges from 0 to m+n-2. Cells in each group listed in decreasing row order.
Spiral traversal — four boundary pointers (top, bottom, left, right); process top row left→right, right col top→bottom, bottom row right→left, left col bottom→top; shrink boundaries after each pass. Terminates when top > bottom or left > right.
Layer-by-layer (onion peeling) — same boundary approach; used for rotating the matrix in-place by cycling one "ring" at a time.
BFS from cell(s) — enqueue source, expand 4-directional neighbors level by level. Level = distance in hops. Mark visited at enqueue.
See breadth-first-search.md for full BFS traversal coverage.
DFS from cell — recursive or stack-based; visits one connected region exhaustively before backtracking.
See depth-first-search.md for full DFS traversal coverage.
Topic-Specific Operations
In-bounds check
Gate every neighbor access: 0 <= nr < m and 0 <= nc < n. The most common source of IndexError in grid problems.
Direction expansion
Pre-declare dirs = [(0,1),(0,-1),(1,0),(-1,0)] and loop for dr, dc in dirs: nr, nc = r+dr, c+dc. Eliminates repetitive if-branches.
90° clockwise rotation (in-place, square matrix)
Transpose then reverse each row. Transpose: M[i][j], M[j][i] = M[j][i], M[i][j] for j > i. Reverse rows: M[i].reverse(). Two-step, O(n²) time, O(1) space.
90° counter-clockwise rotation (in-place) Reverse each row first, then transpose. Equivalent to transpose then reverse each column.
In-place transpose (square matrix)
Swap M[i][j] and M[j][i] for all i < j. Rectangular matrix requires a new array.
2D prefix sum build
P[i][j] = M[i-1][j-1] + P[i-1][j] + P[i][j-1] - P[i-1][j-1]
Rectangle sum (r1,c1) to (r2,c2) (0-indexed): P[r2+1][c2+1] - P[r1][c2+1] - P[r2+1][c1] + P[r1][c1].
Staircase search (sorted matrix)
Start at top-right corner (0, n-1). If M[r][c] == target → found. If M[r][c] > target → move left (c−=1). If M[r][c] < target → move down (r+=1). O(m+n) time.
Key Algorithms
Flood Fill / Connected Components (DFS/BFS)
Identifies all cells reachable from a source with the same property (value, color, island). Visits all 4-directional neighbors meeting the condition, marking them visited. Time O(mn), space O(mn) recursion stack worst case; BFS avoids stack overflow.
Multi-Source BFS
Initialize the BFS queue with all source cells simultaneously at distance 0. A single BFS pass then finds the minimum distance from any source to every cell. Time O(mn). Required whenever the problem asks "distance to nearest X": rotting oranges, 0-1 matrix, walls-and-gates.
See breadth-first-search.md for full multi-source BFS mechanics.
Binary Search on Sorted Row Matrix (LeetCode 74 variant)
Treat the m×n sorted matrix as a flattened sorted array of length mn. Binary search on index mid; convert back: r = mid // n, c = mid % n. Time O(log mn).
Staircase Search (Sorted Matrix — LeetCode 240 variant)
Described under Topic-Specific Operations. Eliminates one row or one column per step; cannot use flattened binary search because the matrix isn't globally sorted in row-major order.
2D Dynamic Programming
Cell (r, c) state depends on (r-1, c) and/or (r, c-1) (and sometimes diagonals). Fill in row-major order. Standard recurrences: dp[r][c] = dp[r-1][c] + dp[r][c-1] (unique paths), dp[r][c] = min(dp[r-1][c], dp[r][c-1]) + cost[r][c] (min-cost path). Time O(mn), space reducible to O(n) with rolling rows.
See dynamic-programming.md for general DP formulation guidance.
Dijkstra on Weighted Grid
Each cell is a graph node; edge weight = cost to enter the neighbor. Min-heap priority queue (cost, r, c); same as standard Dijkstra. Time O(mn log mn). Use when cell traversal costs differ (obstacle weights, varying terrain).
0-1 BFS on Grid
When move cost is either 0 or 1. Use a deque: cost-0 moves go to front (appendleft), cost-1 to back (append). O(mn) — faster than Dijkstra for this special case.
Spiral Order Extraction
Four boundary pointers, shrink after each directional sweep. Returns elements in spiral order. Time O(mn), space O(1) excluding output.
Matrix Rotation (90° CW in-place)
Transpose the matrix, then reverse each row. Two passes, O(n²) total. Key: only works in-place on square matrices — rectangular rotation requires O(mn) extra space.
Advanced Techniques
Multi-Source BFS for Distance Layers
Problem class: "minimum distance from any cell of type X to every other cell"; "time to reach all cells from multiple sources". Mechanism: Pre-load all source cells into the BFS queue at level 0. Standard BFS then propagates outward level by level; each cell's first-visit level is its distance to the nearest source. When to prefer over single-source BFS: whenever there are multiple sources and you want the distance to the nearest one — single-source BFS for each source would be O(k·mn); multi-source collapses it to O(mn). Complexity: O(mn) time and space.
2D Prefix Sum + 2D Difference Array
Problem class: "sum of rectangle subgrid in O(1)"; "apply +v to all cells in a rectangle, then query each cell's final value".
Mechanism: Prefix sum for static queries; difference array for batch range updates. Build difference array D, apply D[r1][c1] += v, D[r1][c2+1] -= v, D[r2+1][c1] -= v, D[r2+1][c2+1] += v, then reconstruct via 2D prefix sum.
When to prefer over naive: any problem with repeated rectangle queries or range updates — naive is O(mn) per query.
Complexity: O(mn) build, O(1) query/update.
In-Place State Encoding
Problem class: simulation problems requiring new state computed from old state (Game of Life, counting live neighbors while updating).
Mechanism: Encode the old and new state together in a single integer using unused bits or values (e.g., 2 = was-dead-now-live, 3 = was-live-now-dead). Read old state with cell & 1; after updating, recover new state with cell >> 1 or a final pass modding by 2.
When to prefer over copy: when the problem explicitly requires in-place O(1) space; otherwise, a copy is simpler and less error-prone.
Complexity: O(mn) time, O(1) extra space.
Union-Find on Grid (Flattened Node IDs)
Problem class: counting connected components with dynamic connectivity; merging islands; tracking group sizes.
Mechanism: Map cell (r, c) to node id r*n + c. Apply union-find with path compression and union by rank. Merge adjacent cells meeting the connection condition.
When to prefer over BFS/DFS: when components merge dynamically (online queries) or when you need to query group size efficiently after each merge. Static connected components are simpler with BFS/DFS.
Complexity: O(mn · α(mn)) ≈ O(mn) effectively.
See arrays.md for Union-Find implementation details (under Advanced Techniques).
Problem Taxonomy
By Problem Category
| Category | What it asks | Key technique |
|---|---|---|
| Connected components | Count distinct islands/regions; label cells | DFS or BFS flood fill |
| Shortest path (unweighted) | Min hops from source to target; cells are 0/1 traversable | BFS; multi-source BFS for multiple sources |
| Shortest path (weighted) | Min cost path; cells have entry costs | Dijkstra; 0-1 BFS when costs ∈ {0,1} |
| Grid DP — counting | Number of distinct paths under constraints | 2D DP (top-left → bottom-right fill) |
| Grid DP — optimization | Min/max cost/sum path from corner to corner | 2D DP with min/max recurrence |
| Grid DP — reachability | Can you reach target? | 2D boolean DP |
| Matrix transformation | Rotate, transpose, reverse in-place | Layer-by-layer, transpose + reverse |
| Spiral/diagonal extraction | Read matrix in spiral or diagonal order | Boundary pointers; group by r±c |
| Search in sorted matrix | Does target exist? | Binary search (flattened) or staircase search |
| Range sum queries | Sum over arbitrary rectangle subgrid | 2D prefix sum |
| Simulation | Game of Life; cascade updates; spreading | In-place encoding; BFS/DFS per step |
| Boundary-connected flood | Mark regions connected to border vs. enclosed | DFS/BFS from border cells inward |
Problem Signal → Technique
| Signal in problem | Likely technique |
|---|---|
| "Number of islands", "count connected regions" | BFS or DFS flood fill |
| "Minimum steps / distance to reach" (grid, unweighted) | BFS |
| "Distance from every cell to nearest X" | Multi-source BFS |
| "Minimum cost path" with varying cell costs | Dijkstra on grid |
| "How many distinct paths" | 2D DP (counting) |
| "Minimum sum path from top-left to bottom-right" | 2D DP (optimization) |
| "Rotate image / rotate matrix 90 degrees" | Transpose + reverse rows |
| "Search target in row-sorted matrix" | Flattened binary search |
| "Search target in row+col sorted matrix" | Staircase search from top-right |
| "Sum of rectangle submatrix" | 2D prefix sum |
| "Cells surrounded by X / mark enclosed regions" | BFS/DFS from border; invert |
| "Update all cells in rectangle, then query" | 2D difference array |
| "Return matrix elements in spiral order" | Four-pointer spiral |
| "Next state depends on neighbor count" | In-place encoding (Game of Life) |
| "Walls and gates", "zombie infection" | Multi-source BFS |
Common Patterns
| Pattern | When it applies | Mechanism |
|---|---|---|
| Direction array | Any 4- or 8-directional neighbor expansion | dirs = [(0,1),(0,-1),(1,0),(-1,0)]; loop to generate neighbors |
| In-bounds guard | All grid traversals | 0 <= nr < m and 0 <= nc < n before every access |
| Visited set / in-place marking | BFS/DFS to avoid revisiting | visited[r][c] = True at enqueue; or overwrite cell value |
| BFS queue pre-loading (multi-source) | Multiple simultaneous start cells | Enqueue all sources before BFS loop begins |
| Four-boundary spiral | Spiral read/write | top, bottom, left, right pointers; shrink after each direction |
| Rolling row (DP space opt.) | Grid DP where dp[r] only depends on dp[r-1] | Replace 2D table with two 1D arrays; iterate right-to-left when needed |
| Flatten index | Union-Find on grid; 1D-indexed BFS | id = r*n + c; r = id//n, c = id%n |
| Diagonal grouping | Diagonal or anti-diagonal iteration | Group by r-c (diagonal) or r+c (anti-diagonal) |
| Border-seeded BFS | Find cells NOT connected to border | BFS/DFS from all border cells; invert the remaining unvisited cells |
| Bit-packed state | In-place simulation needing old + new value | Encode both states in different bits of cell value |
Edge Cases & Pitfalls
-
Empty matrix or zero rows/cols —
if not matrix or not matrix[0]must short-circuit before any index access.matrix[0]on an empty list raisesIndexError. -
Single row or single column — many algorithms assume both dimensions > 1 (e.g., rotation requires square; spiral with one row must handle the bottom and top rows being the same). Guard
if top <= bottomandif left <= rightbefore each sweep direction in spiral code. -
Non-square rotation — rotating a non-square matrix in-place is impossible; it requires a new array. Assuming squareness breaks on m ≠ n inputs.
-
Shallow copy of rows —
[[0]*n]*mcreates m references to the same row. Mutation through one row mutates all. Always use list comprehension:[[0]*n for _ in range(m)]. -
Marking visited at dequeue instead of enqueue — allows the same cell to be enqueued multiple times before processing, giving wrong distances and O(mn²) worst-case complexity. Always mark at enqueue.
-
Off-by-one in prefix sum indexing — the standard
P[i][j]stores the sum of the top-lefti×jsubgrid (1-indexed). Mixing 0-indexed and 1-indexed access is the most common prefix sum bug; choose one convention and stick to it throughout. -
Staircase search starting corner — must start at top-right
(0, n-1)or bottom-left(m-1, 0), not top-left or bottom-right. Starting at top-left means both "go right" and "go down" increase the value, so no element can be eliminated. -
DFS stack overflow on large grids — recursive DFS on a 300×300 grid requires up to 90,000 stack frames. Python's default recursion limit is 1,000. Convert to iterative BFS or increase with
sys.setrecursionlimit. -
In-place encoding corruption — when using values like 2 or 3 as temporary markers, the neighbor-reading code must extract the original value (e.g.,
cell & 1orcell % 2). Reading the encoded value as the original breaks neighbor-count logic. -
Direction array length — accidentally using 8 directions instead of 4 (or vice versa) is silent; connected-component counts will be wrong. Verify
dirslength matches the problem's adjacency definition.
Implementation Notes
- Python
list2D grids require[[val]*n for _ in range(m)]— the*mshortcut creates aliased rows. collections.dequeis mandatory for BFS;list.pop(0)is O(n), turning O(mn) BFS into O(m²n²).- Python's default recursion limit is 1,000; for grids larger than ~31×31, iterative BFS is safer than recursive DFS.
- For 2D prefix sum, allocate
P = [[0]*(n+1) for _ in range(m+1)]to avoid boundary checks inside the build loop. heapqin Python is a min-heap; for Dijkstra on a grid seeking minimum cost, push(cost, r, c)directly. For maximum, negate costs.- When building Union-Find for a grid, size the parent array to
m*n; avoid creating a 2D parent matrix (increases implementation complexity). sys.setrecursionlimit(10**6)before recursive DFS works but adds risk on competitive platforms with strict memory limits — prefer iterative.
Cross-Topic Relations
| Related topic | Specific connection |
|---|---|
| BFS | Shortest path and multi-source distance problems on unweighted grids; see breadth-first-search.md |
| DFS | Flood fill, connected components, word search; see depth-first-search.md |
| Dynamic Programming | Grid DP (unique paths, min-cost path, longest increasing path); see dynamic-programming.md |
| Arrays | 2D prefix sum and difference array build on 1D versions; in-place techniques; see arrays.md |
| Binary Search | Flattened binary search on sorted-row matrix; staircase search on fully-sorted matrix; see binary-search.md |
| Graphs | Grid is an implicit graph; adjacency is 4-directional; all graph algorithms apply |
| Union-Find | Counting connected components dynamically; island merging queries |
| Sorting | Sorting cells by value for Kruskal-style island union; sorting diagonals |
| Heap (Priority Queue) | Dijkstra on weighted grid; finding k-th smallest in sorted matrix |
Interview Reference
Must-Know Problems
Connected components / flood fill
- Flood Fill (733) — starter; basic DFS/BFS from source cell
- Number of Islands (200) — count components; mark visited in-place
- Max Area of Island (695) — track component size during DFS
- Pacific Atlantic Water Flow (417) — reverse flood from both borders; intersection
- Surrounded Regions (130) — border-seeded BFS; invert enclosed cells
Shortest path / BFS distance
- 01 Matrix (542) — multi-source BFS from all 0-cells; distance to nearest zero
- Rotting Oranges (994) — multi-source BFS; time for full spread
- Walls and Gates (286) — multi-source BFS from all gates
- Shortest Path in Binary Matrix (1091) — 8-directional BFS; classic grid shortest path
Grid DP
- Unique Paths (62) — count paths;
dp[r][c] = dp[r-1][c] + dp[r][c-1] - Minimum Path Sum (64) — min-cost path; same recurrence with
min - Unique Paths II (63) — with obstacles; zero out blocked cells
- Dungeon Game (174) — reverse DP from bottom-right to top-left
- Longest Increasing Path in a Matrix (329) — DFS with memoization; topological order
Matrix transformation
- Rotate Image (48) — 90° CW in-place: transpose + reverse rows
- Spiral Matrix (54) — read in spiral order; four-pointer boundary
- Spiral Matrix II (59) — write 1..n² in spiral; same boundary approach
- Set Matrix Zeroes (73) — in-place; use first row/col as markers
Search in sorted matrix
- Search a 2D Matrix (74) — rows sorted, rows globally ordered; flattened binary search
- Search a 2D Matrix II (240) — rows and columns sorted; staircase search O(m+n)
- Kth Smallest Element in a Sorted Matrix (378) — binary search on value range + count
Range queries
- Range Sum Query 2D — Immutable (304) — 2D prefix sum; O(1) queries after O(mn) build
- Count Submatrices With All Ones (1504) — prefix sum + 1D histogram technique
Simulation
- Game of Life (289) — in-place encoding with 2-bit state; decode in final pass
- Word Search (79) — DFS with backtracking; mark visited in-place during recursion
Additional LeetCode Coverage
- Construct Quad Tree (LC 427)
- Diagonal Traverse (LC 498)
- Minimum Falling Path Sum (LC 931)
- Count Square Submatrices with All Ones (LC 1277)
- Count Negative Numbers in a Sorted Matrix (LC 1351)
- Matrix Diagonal Sum (LC 1572)
- Richest Customer Wealth (LC 1672)
- Find a Peak Element II (LC 1901)
- Equal Row and Column Pairs (LC 2352)
- Valid Sudoku (LC 36)
Clarification Questions to Ask
- Is the matrix guaranteed to be non-empty? Can m or n be 0?
- Is the matrix square? (Required for in-place rotation/transpose)
- Are negative values possible? (Affects DP recurrence direction, Dijkstra cost signs)
- Is connectivity 4-directional or 8-directional?
- For path problems: can you revisit cells?
- For search problems: are values guaranteed unique? Sorted rows only, or rows + columns?
- For BFS distance: is the source guaranteed reachable? What if no path exists?
Common Interview Mistakes
- Marking cells visited at dequeue instead of enqueue — allows duplicate queue entries and inflated distances.
- Forgetting to handle single-row or single-column matrices in spiral traversal — the inner left→right and right→left sweeps can double-process the same row.
- Using
[[0]*n]*mfor grid initialization — aliased rows cause mutations to propagate unexpectedly. - Starting staircase search from the wrong corner (top-left or bottom-right instead of top-right) — neither corner allows elimination of a row or a column on each step.
- Rotating a non-square matrix in-place — silently produces wrong results or index errors; requires a new array.
- Reading the encoded state (e.g.,
2) instead of the original state (2 & 1 = 0) in Game of Life — neighbor counts are wrong from the first modified cell onward. - Applying
sys.setrecursionlimitbut still stack-overflowing on large grids — the OS stack limit is below Python's adjusted limit; use iterative BFS for production.
Typical Follow-Up Escalations
- "Now find the minimum path sum with at most k obstacles removed" → BFS/Dijkstra with state
(r, c, obstacles_remaining); O(mn·k) states. - "Now the grid can be very large and sparse" → coordinate compression; use dict representation; BFS on implicit graph.
- "Now support online updates to cell values, still answering rectangle sum queries" → 2D Binary Indexed Tree (Fenwick Tree) for O(log m · log n) point update and prefix query.
- "What if the matrix doesn't fit in memory?" → stream rows; for DP, keep only two rows at a time (rolling array); for BFS, partition the grid.
- "Count islands but cells are added one by one" → Union-Find with flattened ids; merge with already-land neighbors on each insertion.
Read Next
Start reading to get personalized recommendations
Explore Unread
Great job! You've read all available articles