PATTERN 8 OF 22

Matrix / 2D Arrays

Navigate and transform 2D grids using structured traversal patterns — row/column iteration, spiral order, layer-by-layer rotation, and in-place modifications.

Time: O(m*n)

Space: O(1) to O(m*n)

Learn & Reference

Understanding the Pattern

Matrix / 2D Arrays Pattern

Matrices (2D arrays) appear constantly in interviews. The key to solving matrix problems efficiently is recognizing which traversal pattern the problem requires and applying it systematically. Most matrix problems boil down to one of a handful of movement strategies.

Core Concept

A matrix is a 2D grid with m rows and n columns. You access element at row r, column c as matrix[r][c]. The four cardinal directions are (r-1,c), (r+1,c), (r,c-1), (r,c+1). Diagonals add four more: (r-1,c-1), (r-1,c+1), (r+1,c-1), (r+1,c+1).

The 5 Matrix Archetypes

1. Row-Major / Column-Major Traversal

The simplest pattern: iterate every cell in row order or column order. Used for search, counting, and set-zeroes marking.

2. Spiral Traversal

Walk the matrix in a spiral: right across the top row, down the right column, left across the bottom row, up the left column, then shrink the boundary inward and repeat. Track four boundaries: top, bottom, left, right.

3. Layer-by-Layer Processing (Rotate Image)

Process the matrix in concentric rectangular layers from outside to inside. Each layer has layer_size - 1 rotations. This is the key to in-place 90-degree rotation: for each position in a layer, do a 4-way swap.

4. Transpose + Reverse (Rotation Shortcut)

Rotate 90 degrees clockwise = transpose the matrix (swap matrix[i][j] with matrix[j][i]), then reverse each row. This is simpler to code than the 4-way swap and runs in O(m*n) time.

5. Binary Search on Sorted Matrix

When a matrix is sorted (each row sorted, first element of each row > last element of previous row), treat it as a flattened sorted array. Map index mid to (mid / n, mid % n) and run standard binary search.

Boundary Checking

Almost every matrix problem requires bounds checking. Before accessing matrix[r][c], verify:

0 <= r < rows
0 <= c < cols

A common helper is a direction array: dirs = [(0,1),(0,-1),(1,0),(-1,0)] to iterate neighbors cleanly.

In-Place Modifications

Many problems require O(1) extra space. Common tricks:

Use the matrix itself as storage: mark visited cells with a sentinel value (e.g., set to 0 or -1)
First row/column as flags: for "set matrix zeroes", use the first row and column to record which rows/columns need zeroing
Swap in cycles: for rotation, swap 4 elements at a time in a cycle

When Matrix Pattern Fails

When the grid represents a graph with complex connectivity (use BFS/DFS instead)
When you need to find shortest paths in a weighted grid (use Dijkstra)
When the matrix is sparse and better represented as a hash map of coordinates

Common Mistakes

Mixing up rows and columns: matrix[row][col] not matrix[col][row]. Rows = matrix.length, Cols = matrix[0].length
Off-by-one in spiral traversal: forgetting to update boundaries after each direction, or not checking top <= bottom and left <= right before the return passes
Modifying while iterating: for set-zeroes, if you zero out cells immediately, you lose information about which cells were originally zero. Mark first, then zero
Assuming square matrix: many problems have m != n. Always use separate row and column counts
Forgetting edge cases: empty matrix, single row, single column, 1x1 matrix
Wrong rotation direction: clockwise 90 = transpose + reverse rows. Counter-clockwise 90 = transpose + reverse columns (or reverse rows then transpose)

When to Use

Given an m x n matrix...

Spiral order traversal

Rotate image / matrix 90 degrees

Search in a sorted 2D matrix

Set matrix zeroes

Transpose a matrix

Traverse diagonals of a matrix

In-place modification of a 2D grid

Layer-by-layer or ring-by-ring processing

Problems involving coordinates (row, col) on a grid

Any problem where the input is a 2D array and doesn't require BFS/DFS graph search

Template

1# --- Matrix Traversal (Row-Major) ---
2def traverse(matrix):
3    """Visit every cell in row-major order"""
4    if not matrix or not matrix[0]:
5        return
6    m, n = len(matrix), len(matrix[0])
7    for r in range(m):
8        for c in range(n):
9            process(matrix[r][c])
10
11# --- Spiral Order Traversal ---
12def spiral_order(matrix):
13    """Return all elements in spiral order"""
14    result = []
15    if not matrix or not matrix[0]:
16        return result
17    top, bottom = 0, len(matrix) - 1
18    left, right = 0, len(matrix[0]) - 1
19
20    while top <= bottom and left <= right:
21        # Traverse right across top row
22        for c in range(left, right + 1):
23            result.append(matrix[top][c])
24        top += 1
25
26        # Traverse down right column
27        for r in range(top, bottom + 1):
28            result.append(matrix[r][right])
29        right -= 1
30
31        # Traverse left across bottom row
32        if top <= bottom:
33            for c in range(right, left - 1, -1):
34                result.append(matrix[bottom][c])
35            bottom -= 1
36
37        # Traverse up left column
38        if left <= right:
39            for r in range(bottom, top - 1, -1):
40                result.append(matrix[r][left])
41            left += 1
42
43    return result
44
45# --- Rotate Matrix 90° Clockwise (In-Place) ---
46def rotate(matrix):
47    """Rotate n x n matrix clockwise: transpose then reverse rows"""
48    n = len(matrix)
49    # Step 1: Transpose
50    for i in range(n):
51        for j in range(i + 1, n):
52            matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
53    # Step 2: Reverse each row
54    for row in matrix:
55        row.reverse()

{ }

Syntax Reference

1# === Matrix Creation ===
2rows, cols = 3, 4
3matrix = [[0] * cols for _ in range(rows)]     # 3x4 of zeros
4# WRONG: [[0]*cols]*rows  (all rows share same list!)
5
6# === Dimensions ===
7m = len(matrix)          # rows
8n = len(matrix[0])       # cols
9
10# === Access ===
11val = matrix[r][c]       # get element
12matrix[r][c] = val       # set element
13
14# === Row-Major Traversal ===
15for r in range(m):
16    for c in range(n):
17        process(matrix[r][c])
18
19# === Column-Major Traversal ===
20for c in range(n):
21    for r in range(m):
22        process(matrix[r][c])
23
24# === 4-Directional Neighbors ===
25dirs = [(0, 1), (0, -1), (1, 0), (-1, 0)]
26for dr, dc in dirs:
27    nr, nc = r + dr, c + dc
28    if 0 <= nr < m and 0 <= nc < n:
29        process(matrix[nr][nc])
30
31# === Transpose (in-place, square only) ===
32for i in range(len(matrix)):
33    for j in range(i + 1, len(matrix)):
34        matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
35
36# === Reverse Each Row ===
37for row in matrix:
38    row.reverse()

📋

Common Recipes

1# --- Spiral Traversal ---
2def spiral_order(matrix):
3    result = []
4    if not matrix:
5        return result
6    top, bottom = 0, len(matrix) - 1
7    left, right = 0, len(matrix[0]) - 1
8
9    while top <= bottom and left <= right:
10        # Right across top row
11        for c in range(left, right + 1):
12            result.append(matrix[top][c])
13        top += 1
14
15        # Down right column
16        for r in range(top, bottom + 1):
17            result.append(matrix[r][right])
18        right -= 1
19
20        # Left across bottom row
21        if top <= bottom:
22            for c in range(right, left - 1, -1):
23                result.append(matrix[bottom][c])
24            bottom -= 1
25
26        # Up left column
27        if left <= right:
28            for r in range(bottom, top - 1, -1):
29                result.append(matrix[r][left])
30            left += 1
31
32    return result
33
34# --- Rotate 90 Degrees Clockwise (In-Place) ---
35def rotate(matrix):
36    n = len(matrix)
37    # Transpose
38    for i in range(n):
39        for j in range(i + 1, n):
40            matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
41    # Reverse each row
42    for row in matrix:
43        row.reverse()
44
45# --- Set Matrix Zeroes (O(1) Space) ---
46def set_zeroes(matrix):
47    m, n = len(matrix), len(matrix[0])
48    first_row_zero = any(matrix[0][c] == 0 for c in range(n))
49    first_col_zero = any(matrix[r][0] == 0 for r in range(m))
50
51    # Use first row/col as flags
52    for r in range(1, m):
53        for c in range(1, n):
54            if matrix[r][c] == 0:
55                matrix[r][0] = 0
56                matrix[0][c] = 0
57
58    # Zero cells based on flags
59    for r in range(1, m):
60        for c in range(1, n):
61            if matrix[r][0] == 0 or matrix[0][c] == 0:
62                matrix[r][c] = 0
63
64    # Handle first row and col
65    if first_row_zero:
66        for c in range(n):
67            matrix[0][c] = 0
68    if first_col_zero:
69        for r in range(m):
70            matrix[r][0] = 0

O(n)

Complexity

Operation	Time	Space
Full traversal (row/col major)	O(m*n)	O(1)
Spiral traversal	O(m*n)	O(1) extra
Rotate 90 (transpose+reverse)	O(n^2)	O(1)
Search sorted matrix	O(log(m*n))	O(1)
Set matrix zeroes	O(m*n)	O(1)
Element access	O(1)	O(1)

Watch Out

✗When the grid represents a graph with complex connectivity (use BFS/DFS instead)
✗When you need to find shortest paths in a weighted grid (use Dijkstra)
✗When the matrix is sparse and better represented as a hash map of coordinates
✗Mixing up rows and columns: `matrix[row][col]` not `matrix[col][row]`. Rows = `matrix.length`, Cols = `matrix[0].length`
✗Off-by-one in spiral traversal: forgetting to update boundaries after each direction, or not checking `top <= bottom` and `left <= right` before the return passes
✗Modifying while iterating: for set-zeroes, if you zero out cells immediately, you lose information about which cells were originally zero. Mark first, then zero
✗Assuming square matrix: many problems have `m != n`. Always use separate row and column counts
✗Forgetting edge cases: empty matrix, single row, single column, 1x1 matrix
✗Wrong rotation direction: clockwise 90 = transpose + reverse rows. Counter-clockwise 90 = transpose + reverse columns (or reverse rows then transpose)

PRACTICE PROBLEMS

Linked Lists

Trees (DFS)