Matrix Manipulation (In-Place Tricks)
The Intuition
A matrix is just a grid of numbers, but interview problems on matrices test something subtle: can you mutate the grid in place without allocating a copy? Three patterns show up over and over, one for each of the canonical Blind 75 matrix problems.
The code below works through all three.
Set Matrix Zeroes (LC 73). Given an m x n matrix, set every cell in the same row and column as any zero to zero, in place, with O(1) extra memory. The trick is to repurpose the first row and first column of the input as bookkeeping. Whenever you find a zero deep in the matrix, mark its row and column by writing zero to the corresponding cell in row 0 or column 0. The only catch is that those marker cells were also part of the input, so two boolean flags record up front whether the first row or first column themselves originally contained a zero. After the bulk of the matrix is processed using the markers, the first row and column are zeroed last using those two flags.
Rotate Image (LC 48). Given an n x n matrix, rotate it 90 degrees clockwise in place. Two simple steps do the work: transpose the matrix (swap across the main diagonal), then reverse each row left to right. The composition of those two operations is exactly the rotation. For 90 degrees counterclockwise, transpose then reverse each column instead.
Spiral Matrix (LC 54). Given an m x n matrix, return all elements in spiral order: right across the top, down the right side, left along the bottom, up the left side, then peel inward. Maintain four pointers (top, bottom, left, right) and walk one edge at a time, shrinking the corresponding boundary after each pass. The two if checks before the bottom and left passes are not optional. They handle the case where shrinking the row range or column range collapses to a single line, where you might otherwise re-walk it.
- Problem says "modify in-place" or restricts extra space to O(1)
- Square matrix rotation, regardless of angle
- Need to visit cells in a non-trivial order (spiral, diagonal, anti-diagonal)
- Boundary or border processing of a 2D grid
- Need to preserve the original matrix while computing the result
- Sparse matrix where most cells are empty (use a different data structure)
- The matrix represents a graph and you need traversal (use BFS/DFS instead)
Variations:
- Use markers stored elsewhere: If you cannot touch the first row and column, you can use a single bit per row/column packed into one variable (rare in interviews but elegant).
- 180 degree rotation: Reverse each row, then reverse the order of rows. Or rotate 90 twice.
- Diagonal traversal: Replace the four boundaries with a single anti-diagonal index
d = i + jand walk all cells with the samed.
- Empty matrix or empty row
- Single row or single column
- 1x1 matrix
- Already-rotated input
- Matrix with all zeros (Set Matrix Zeroes still has to handle this without infinite loops)
Key Points
- •Use the matrix itself for state instead of a copy
- •First row and first column can act as marker flags
- •Transpose then reverse equals 90 degree rotation
- •Track four boundaries (top, bottom, left, right) for spiral traversal
- •Always handle the marker storage separately at the end
Code Template
1 # Set Matrix Zeroes (LC 73). O(1) extra space using first row and column as flags.
2 def set_zeroes(matrix):
3 if not matrix or not matrix[0]:
4 return
5 rows, cols = len(matrix), len(matrix[0])
6 first_row_zero = any(matrix[0][j] == 0 for j in range(cols))
7 first_col_zero = any(matrix[i][0] == 0 for i in range(rows))
8
9 for i in range(1, rows):
10 for j in range(1, cols):
11 if matrix[i][j] == 0:
12 matrix[i][0] = 0
13 matrix[0][j] = 0
14
15 for i in range(1, rows):
16 for j in range(1, cols):
17 if matrix[i][0] == 0 or matrix[0][j] == 0:
18 matrix[i][j] = 0
19
20 if first_row_zero:
21 for j in range(cols):
22 matrix[0][j] = 0
23 if first_col_zero:
24 for i in range(rows):
25 matrix[i][0] = 0
26
27 # Rotate Image (LC 48). 90 degree clockwise in-place.
28 def rotate(matrix):
29 n = len(matrix)
30 for i in range(n):
31 for j in range(i + 1, n):
32 matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
33 for row in matrix:
34 row.reverse()
35
36 # Spiral Matrix (LC 54). Walk four shrinking boundaries.
37 def spiral_order(matrix):
38 if not matrix or not matrix[0]:
39 return []
40 result = []
41 top, bottom = 0, len(matrix) - 1
42 left, right = 0, len(matrix[0]) - 1
43 while top <= bottom and left <= right:
44 for j in range(left, right + 1):
45 result.append(matrix[top][j])
46 top += 1
47 for i in range(top, bottom + 1):
48 result.append(matrix[i][right])
49 right -= 1
50 if top <= bottom:
51 for j in range(right, left - 1, -1):
52 result.append(matrix[bottom][j])
53 bottom -= 1
54 if left <= right:
55 for i in range(bottom, top - 1, -1):
56 result.append(matrix[i][left])
57 left += 1
58 return resultCommon Mistakes
- Forgetting to record whether the first row or first column themselves contained a zero before using them as markers
- Off-by-one errors when shrinking spiral boundaries
- Trying to rotate by copying into a new matrix when the problem says in-place
- Reading and writing to the same row simultaneously without a temp variable