FundamentalsData structureaka 2D array, grid, table, two-dimensional array

Matrix (2D Array)

A rectangular grid of values indexed by (row, column), stored as an array of rows or one flattened row-major array.

Progress

Definition

A matrix is a two-dimensional Array: m rows by n columns, addressed as a[r][c]. It appears in three guises in interviews — as a grid to search (islands, mazes, rotting oranges), as a DP table (edit distance, unique paths), and as an Adjacency Matrix for dense graphs.

Physically the memory is still one-dimensional. Row-major layout stores row 0, then row 1, and so on, so a[r][c] lives at offset r * n + c. This makes iterating row by row cache-friendly and column by column slow; it also lets you treat a sorted matrix as a flat sorted array for Binary Search.

Grid problems are graph problems in disguise: each cell is a vertex with up to four (or eight) neighbours given by direction offsets. Breadth-First Search (BFS), Depth-First Search (DFS), and Union-Find (Disjoint Set Union) therefore apply directly without ever building an explicit graph.

2Dgridrow-majorneighboursDP tableadjacency

Intuition

A mental model before the formal terms.

Picture a spreadsheet. Every cell has a row letter and column number; you can jump to C7 instantly. But the spreadsheet file on disk is a single long stream: all of row 1, then all of row 2. Reading down a column means jumping across the stream repeatedly, which is why "loop over rows outside, columns inside" is the fast order.

For grid searches, imagine standing on a tile and being able to step up, down, left or right. The four offsets (-1,0) (1,0) (0,-1) (0,1) are the "edges" of an implicit graph — you never write the adjacency down, you just compute it.

How it works

Allocate: either an array of m row-arrays ([[0]*n for _ in range(m)]) or one array of length m * n plus the dimension n.
get(r, c) / set(r, c, v): bounds-check 0 <= r < m and 0 <= c < n, then index rows[r][c] or flat[r * n + c].
Neighbours: for (dr, dc) in [(-1,0),(1,0),(0,-1),(0,1)] compute (r+dr, c+dc) and skip out-of-bounds cells. Add diagonals for 8-connectivity.
Traversal patterns: row-major scan; column-major scan; spiral (shrinking bounds top/bottom/left/right); diagonals (r + c constant).
Transformations: transpose swaps a[r][c] with a[c][r]; rotating 90° clockwise = transpose then reverse each row; both in place for square matrices.
Flattening: (r, c) -> r * n + c and back r = k / n, c = k % n, enabling binary search over a row-and-column sorted matrix.

Why it works

The row-major address formula r * n + c is a bijection between (r, c) pairs and 0..m*n-1, so 2D indexing is still O(1) and any 1D array algorithm can be reused after flattening.

Grid traversals visit each cell at most once with a visited mark (or by mutating the cell), so BFS/DFS over an m × n grid is O(m·n) — there are at most 4·m·n implicit edges.

DP tables work on matrices because each cell depends only on already-computed neighbours (up/left), so a row-major fill order is a valid topological order.

Operations

Operation	Description	Cost
get(r, c) / set(r, c, v)	Direct indexing after bounds checks; `flat[r * n + c]` for a flattened store.	O(1)
neighbours(r, c)	Apply 4 (or 8) direction offsets and filter out-of-bounds.	O(1)
row(r) / column(c)	Read all `n` (or `m`) cells; columns are cache-unfriendly in row-major layout.	O(n) / O(m)
traverse	Visit every cell, row-major for locality.	O(m·n)
transpose()	Swap `a[r][c]` and `a[c][r]` for `c > r` (in place if square).	O(m·n)
rotate90()	Transpose then reverse each row.	O(n²)
search(v)	Full scan; `O(m + n)` staircase search if rows and columns are sorted; `O(log(m·n))` if fully sorted.	O(m·n)

Recognition

How to tell a problem wants this.

Input described as a "grid", "board", "image", "maze", "map", or a 2D array of 0s and 1s.
Questions about connected regions ("islands"), shortest path in a grid, flood fill, or spreading (rotting oranges).
Two-sequence DP (edit distance, LCS) or "number of paths from top-left to bottom-right".
Rotation, transpose, spiral order, or "set zeroes in place" — pure index manipulation.

“sum of subarray” → Prefix Sum “minimum steps” → Breadth-First Search “connected groups” → Depth-First Search “all combinations” → Backtracking “number of ways” → Dynamic Programming

Interactive demo

Play, step, change the input. ← → and space work too.

No interactive visualization for this topic yet

Related visualizations are linked under Related.

Pseudocode

1class Matrix(m, n):
2  flat = allocate(m * n)
3  get(r, c): assert inBounds(r, c); return flat[r * n + c]
4  set(r, c, v): assert inBounds(r, c); flat[r * n + c] = v
5  neighbours(r, c):
6    for (dr, dc) in [(-1,0),(1,0),(0,-1),(0,1)]:
7      nr, nc = r + dr, c + dc
8      if 0 <= nr < m and 0 <= nc < n: yield (nr, nc)
9  transpose(): out = Matrix(n, m); for r, c: out[c][r] = this[r][c]; return out
10  rotate90(): transpose in place, then reverse each row

Implementation

1from typing import Iterator
2 
3 
4class Matrix:
51 · Row-major flat storage
6    def __init__(self, rows: int, cols: int) -> None:
7        self.m, self.n = rows, cols
8        self._flat: list[int] = [0] * (rows * cols)  # (r, c) -> flat[r * n + c]
9 
102 · Bounds-checked get/set
11    def in_bounds(self, r: int, c: int) -> bool:
12        return 0 <= r < self.m and 0 <= c < self.n
13 
14    def get(self, r: int, c: int) -> int:
15        if not self.in_bounds(r, c):
16            raise IndexError((r, c))
17        return self._flat[r * self.n + c]
18 
19    def set(self, r: int, c: int, v: int) -> None:
20        if not self.in_bounds(r, c):
21            raise IndexError((r, c))
22        self._flat[r * self.n + c] = v
23 
243 · Four-directional neighbours
25    def neighbours(self, r: int, c: int) -> Iterator[tuple[int, int]]:
26        for dr, dc in ((-1, 0), (1, 0), (0, -1), (0, 1)):
27            nr, nc = r + dr, c + dc
28            if self.in_bounds(nr, nc):
29                yield nr, nc
30 
314 · Transpose into a new matrix
32    def transpose(self) -> "Matrix":
33        t = Matrix(self.n, self.m)
34        for r in range(self.m):
35            for c in range(self.n):
36                t._flat[c * self.m + r] = self._flat[r * self.n + c]
37        return t
38 
395 · Rotate a square matrix 90° clockwise in place
40    def rotate90(self) -> None:
41        if self.m != self.n:
42            raise ValueError("rotate90 needs a square matrix")
43        n, f = self.n, self._flat
44        for r in range(n):
45            for c in range(r + 1, n):
46                f[r * n + c], f[c * n + r] = f[c * n + r], f[r * n + c]
47        for r in range(n):
48            f[r * n:(r + 1) * n] = f[r * n:(r + 1) * n][::-1]

Walkthrough

A flat list[int] of length rows * cols holds the cells; r * n + c is the index.
in_bounds uses chained comparisons 0 <= r < self.m, a Python-only readability win.
neighbours is a generator: it yields in-bounds cells lazily instead of building a list.
transpose copies each cell to its mirror in a new matrix; list(zip(*rows)) is the idiom for nested lists.
rotate90 swaps across the diagonal with tuple assignment, then reverses each row using slice assignment.

Complexity (this implementation)

time O(1) get/set, O(m*n) transpose/rotate · space O(m*n)

Slice assignment in rotate90 allocates a temporary reversed copy per row — O(n) extra per row, freed immediately. NumPy stores the matrix as a dense C block.

Language notes

Build nested grids with [[0] * n for _ in range(m)], never [[0] * n] * m.
zip(*grid) transposes a nested list in one expression; [row[::-1] for row in zip(*grid)] rotates clockwise.
NumPy (np.rot90, .T) is the production tool; interview code uses nested lists.

Common mistakes in this language

Aliased rows from [[0] * n] * m.
Using grid[r][c] with r = -1 — Python wraps to the last row silently instead of failing.
Confusing len(grid) (rows) and len(grid[0]) (cols).

Language differences that matter here

Negative indices: Python wraps grid[-1] to the last row silently; C++ is undefined behaviour; JS returns undefined — always bounds-check explicitly.
Row aliasing traps exist in JS (fill(array)) and Python ([[0]*n]*m) but not in C++ (vector<vector<int>>(m, vector<int>(n)) copies each row).
Python has one-line transpose via zip(*grid); C++ and JS need explicit loops or a library.
Memory layout: C++ flat vectors and NumPy are contiguous; JS nested arrays and Python nested lists scatter rows across the heap.

Complexity

Operation	Average	Worst	Note
Access	O(1)	O(1)
Search	O(m·n)	O(m·n)	O(m + n) staircase if rows and columns are sorted.
Insert	O(m·n)	O(m·n)	Inserting a row or column shifts everything after it.
Delete	O(m·n)	O(m·n)
Update	O(1)	O(1)
Traverse	O(m·n)	O(m·n)
Transpose / Rotate	O(m·n)	O(m·n)
Neighbours	O(1)	O(1)	Constant 4 or 8 offsets.
Space	O(m·n)

Advantages & disadvantages

Advantages

O(1) access to any cell and to its neighbours by index arithmetic.
Natural representation for grids, images, DP tables and dense graphs.
Contiguous rows give fast row-wise scans and simple flattening to 1D.

Disadvantages

Always Θ(m·n) memory, even when most cells are empty — a sparse grid or graph is better stored as a Hash Map or Adjacency List.
Inserting/removing a row or column is O(m·n).
Column-wise access has poor locality in row-major layout.
Jagged (ragged) rows break the address formula and many built-in assumptions.

Use cases

Grid search problems: number of islands, flood fill, shortest path in binary matrix, rotting oranges.
DP tables: Edit Distance, Longest Common Subsequence, Grid DP unique paths, 0/1 Knapsack tables.
Adjacency Matrix for dense graphs and Floyd-Warshall distance tables.
2D prefix sums (2D Prefix Sum) for O(1) rectangle-sum queries.
Images, game boards (sudoku, N-queens), spreadsheets.

Use it when

Dense 2D data where most cells are meaningful: images, boards, DP tables.
Grid graph problems — treat cells as vertices and use BFS/DFS with direction offsets.
Dense graphs (E ≈ V²) or algorithms that need O(1) edge lookup (Floyd-Warshall).

Avoid it when

Sparse grids or graphs — Θ(m·n) memory is wasteful; store only occupied cells in a Hash Map or use an Adjacency List.
Frequent row/column insertions — use a list of rows or a different structure.
Huge coordinates (up to 10^9) — compress coordinates or use a map keyed by (r, c).

Alternatives

Array Adjacency List Hash Map Adjacency Matrix

Common mistakes

Creating rows with [[0] * n] * m in Python — all rows alias the same list.
Swapping r and c (or m and n) in bounds checks for non-square matrices.
Forgetting to mark cells visited before enqueueing in BFS, causing duplicate work or infinite loops.
Rotating with a copy when the question demands in-place, or transposing over all (r, c) pairs and undoing the swap.
Iterating columns in the outer loop for large matrices — correct but several times slower due to cache misses.

Interview patterns

Flood fill / island counting with DFS or BFS over 4-neighbours.
Multi-source BFS from all starting cells at once (rotting oranges, walls and gates).
DP fill in row-major order where dp[r][c] depends on dp[r-1][c] and dp[r][c-1].
Staircase search from the top-right corner in a row- and column-sorted matrix.
Spiral traversal with four shrinking boundaries; rotate via transpose + reverse.
Use the first row/column as marker storage to achieve O(1) extra space (set matrix zeroes).

Interview questions on this

Recognizing the approach from an array and a targetIntermediate
Deciding whether O(n²) can be improvedIntermediate
Choosing between BFS, DFS, Dijkstra and DPAdvanced
Stack versus queueBeginner

Mock interviews

Interview problems

Range Sum Query 2D — Immutablemedium Number of Islandsmedium Shortest Path in Binary Matrixmedium Rotting Orangesmedium N-Queenshard Word Searchmedium Sudoku Solverhard Unique Pathsmedium