Matrix and Grid Manipulation

Matrix questions are rarely about algorithms. They are about index discipline under pressure: can you rotate a grid without a scratch copy, walk a spiral without re-visiting a row, or mark rows and columns for deletion without a second array to mark them in?

Interviewers like them precisely because they are hard to bluff. There is no clever insight to recall — either your loop bounds are right or your output is scrambled. This page gives you the three reusable tricks that cover almost the whole family.

What you’ll learn

• Transpose + reverse — rotation without allocating a second matrix.
• The four-boundary template that makes spiral traversal off-by-one-proof.
• Using the matrix’s own first row and column as $O(1)$ marker storage.
• Why “read and write in the same pass” is the recurring bug, and the two ways round it.
• Three real LeetCode problems solved in the browser: 48, 54, 73.

The cue

You are looking at a matrix-manipulation problem when…

• The verb is geometric: rotate, transpose, spiral, flip, shift, diagonal — 48, 54, 59, 498, 867.
• You are told to do it “in place” or with $O(1)$ extra space — 48, 73, 289.
• Cells are updated based on neighbours, so reads and writes collide — 289 Game of Life.
• It is a grid traversal looking for regions or shortest paths — that is a different pattern: see Grid Traversal, Islands and Flood Fill.

The distinction matters: this page is about rearranging a grid. Searching a grid is BFS/DFS.

Trick 1 — rotate by transpose, then reverse

Rotating 90° clockwise in place looks like it needs four-way cyclic swaps. It does not. It decomposes into two trivially correct passes:

rotate_in_place.py

def rotate(matrix):
    n = len(matrix)
 
    for i in range(n):                  # 1. transpose: swap across the diagonal
        for j in range(i + 1, n):       #    j starts at i+1, NOT 0
            matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
 
    for row in matrix:                  # 2. reverse each row
        row.reverse()
 
    return matrix
 
 
print(rotate([[1, 2, 3], [4, 5, 6], [7, 8, 9]]))
# [[7, 4, 1], [8, 5, 2], [9, 6, 3]]

j must start at i + 1

Starting the inner loop at 0 swaps every pair twice, which restores the original matrix — you get a no-op transpose and a final answer that is just each row reversed. Iterating strictly above the diagonal is what makes it a transpose.

The other three rotations are the same two moves in different combinations:

Rotation	Recipe
90° clockwise	transpose, then reverse each row
90° counter-clockwise	transpose, then reverse each column (i.e. matrix.reverse())
180°	reverse each row and reverse the row order

Trick 2 — four boundaries for spiral traversal

Track top, bottom, left, right. Walk one edge, then shrink that boundary inward. The whole difficulty is in two guards.

spiral_order.py

def spiral_order(matrix):
    if not matrix or not matrix[0]:
        return []
 
    top, bottom = 0, len(matrix) - 1
    left, right = 0, len(matrix[0]) - 1
    out = []
 
    while top <= bottom and left <= right:
        for c in range(left, right + 1):            # left -> right along the top
            out.append(matrix[top][c])
        top += 1
 
        for r in range(top, bottom + 1):            # top -> bottom down the right
            out.append(matrix[r][right])
        right -= 1
 
        if top <= bottom:                           # GUARD: row not already taken
            for c in range(right, left - 1, -1):    # right -> left along the bottom
                out.append(matrix[bottom][c])
            bottom -= 1
 
        if left <= right:                           # GUARD: column not already taken
            for r in range(bottom, top - 1, -1):    # bottom -> top up the left
                out.append(matrix[r][left])
            left += 1
 
    return out
 
 
print(spiral_order([[1, 2, 3], [4, 5, 6], [7, 8, 9]]))
# [1, 2, 3, 6, 9, 8, 7, 4, 5]

The two guards are the entire problem

Without if top <= bottom and if left <= right, a single remaining row or column gets traversed twice — once by the rightward pass and again by the leftward one.

Test it on [[1,2,3]] (one row) and [[1],[2],[3]] (one column). Both must return [1, 2, 3]. An unguarded version returns [1,2,3,2,1]-style garbage. These two inputs are the fastest way to check a spiral implementation, yours or someone else’s.

Trick 3 — the matrix as its own marker store

“Set entire row and column to zero wherever you find a zero” has an obvious $O(m + n)$ solution: collect the row and column indices in two sets, then apply. The $O(1)$-space version stores those same flags in row 0 and column 0 of the matrix itself.

The catch: row 0 and column 0 are also real data, and they intersect at matrix[0][0], which cannot flag both. So handle them separately with two booleans, do the interior, then finish the borders last.

Visual intuition

Most “matrix” problems are really graph problems in a 2-D costume. Recognising that is worth more than memorising any traversal:

gridA grid is a graph — cells are nodes, adjacency is edgesO(rows x cols)

0◉

queue

0,0

start0,0goal4,4visited1

1def shortest_path(grid, start, end):2    q = deque([(start, 0)])3    seen = {start}4    while q:5        (r, c), d = q.popleft()6        if (r, c) == end:7            return d               # first arrival IS shortest8        for dr, dc in DIRS:9            nr, nc = r + dr, c + dc10            if in_bounds and grid[nr][nc] != '#' and (nr, nc) not in seen:11                seen.add((nr, nc))12                q.append(((nr, nc), d + 1))13    return -1

setupEach cell will be labelled with its distance from the start. BFS fills outward in rings, so the first time it touches a cell that distance is already the shortest — no revisiting, no relaxation.

Play‹›1/19⟲

Cells are marked visited on ENQUEUE, not on dequeue. Marking on dequeue lets the same cell enter the queue several times, which is the standard way this degrades from linear to quadratic.

Complexity

Operation	Time	Space
Full traversal (BFS or DFS)	$O(rc)$	$O(rc)$ worst case for the frontier
Transpose-and-reverse rotation	$O(rc)$	$O(1)$ in place
Spiral order	$O(rc)$	$O(1)$ beyond the output
Set-matrix-zeroes, using row 0 and column 0 as markers	$O(rc)$	$O(1)$

The recurring theme is that $O(1)$ space is almost always achievable and almost always the follow-up. Naive solutions allocate a second matrix or a set of rows and columns to clear; the in-place versions reuse the matrix itself as storage.

The variant map

Variant	The move	Canonical problem
Rotate 90°	Transpose, then reverse rows	48 Rotate Image
Transpose (non-square)	Must allocate — dimensions change	867 Transpose Matrix
Spiral read	Four boundaries + two guards	54 Spiral Matrix
Spiral write	Same walk, assigning 1..n² instead of reading	59 Spiral Matrix II
Diagonal walk	Cells on a diagonal share r + c; bucket by that sum	498 Diagonal Traverse
Flag in place	Use row 0 / column 0 as marker storage	73 Set Matrix Zeroes
Simultaneous update	Encode next state in spare bits, or use a second value	289 Game of Life

The read/write collision, and the two ways out

Several of these problems update cells based on other cells’ original values. Writing as you read corrupts the input mid-pass.

Two standard escapes:

1. Two passes — first pass records what to change, second applies it (LC 73 uses the borders as the record).
2. Encode both states at once — LC 289 keeps the old state in bit 0 and the new state in bit 1, so cell & 1 is the present and cell >> 1 is the future. One extra pass shifts everything into place.

If an interviewer asks for $O(1)$ space on a neighbour-based update, they are asking for one of these two.

Practice — real LeetCode problems

LC 48 — Rotate Image · Medium

Problem. Given an n x n matrix, rotate it 90° clockwise in place. You must not allocate another matrix.

Constraints. n == len(matrix) == len(matrix[i]), 1 <= n <= 20, -1000 <= matrix[i][j] <= 1000.

Examples. [[1,2,3],[4,5,6],[7,8,9]] gives [[7,4,1],[8,5,2],[9,6,3]]

pch.exerciseTag pch.exerciseTitle

Editorial — approach, complexity, follow-ups

A clockwise rotation sends (r, c) to (c, n-1-r). Doing that as a single four-way cyclic swap over each ring works, but the index expressions are easy to get wrong under pressure.

Decomposing is strictly better: transpose sends (r, c) to (c, r), and reversing each row then sends (c, r) to (c, n-1-r). Composition gives exactly the rotation, and each pass is individually obvious.

Time $O(n^2)$ — unavoidable, every element moves. Space $O(1)$.

Follow-ups you should expect: “Counter-clockwise?” — transpose, then reverse the order of the rows (matrix.reverse()). “180°?” — reverse rows and reverse row order; no transpose. “Non-square?” — a rotation changes the dimensions, so in-place is impossible; allocate an n x m result. “Do the ring-based four-way swap” — iterate for i in range(n // 2) over rings and for j in range(i, n - 1 - i) within a ring, rotating four cells at a time; worth knowing but not worth preferring.

LC 54 — Spiral Matrix · Medium

Problem. Given an m x n matrix, return all its elements in spiral order.

Constraints. 1 <= m, n <= 10, -100 <= matrix[i][j] <= 100.

Examples. [[1,2,3],[4,5,6],[7,8,9]] gives [1,2,3,6,9,8,7,4,5] · [[1,2,3,4],[5,6,7,8],[9,10,11,12]] gives [1,2,3,4,8,12,11,10,9,5,6,7]

pch.exerciseTag pch.exerciseTitle

Editorial — approach, complexity, follow-ups

Four boundaries, four walks, shrink after each. The outer condition top <= bottom and left <= right stops when the unvisited region is empty.

Time $O(m \cdot n)$. Space $O(1)$ beyond the output.

The two guards handle the degenerate end state. After the top row and right column are consumed, the remaining region can be empty in one dimension. If a single row is left, top has already passed bottom after the first walk, so the bottom walk must be skipped — otherwise it re-emits that row backwards. The included [[1,2,3]] and [[1],[2],[3]] cases fail loudly without the guards, which is exactly why they are in the test.

An alternative that some people find easier to defend: keep a directions = [(0,1),(1,0),(0,-1),(-1,0)] cycle and a visited set, turning right whenever the next cell is out of bounds or already seen. It is $O(m \cdot n)$ space rather than $O(1)$, but it has no boundary arithmetic at all — a reasonable trade if you are more confident with it.

Follow-ups you should expect: “Generate a spiral instead of reading one (LC 59)?” — identical walk, assign 1..n² as you go. “Spiral counter-clockwise?” — reorder the four walks. “Diagonal order (LC 498)?” — different structure entirely: cells with equal r + c form a diagonal, so bucket by that sum and reverse alternate buckets.

LC 73 — Set Matrix Zeroes · Medium

Problem. Given an m x n matrix, if an element is 0, set its entire row and column to 0. Do it in place.

Constraints. 1 <= m, n <= 200, -2^31 <= matrix[i][j] <= 2^31 - 1. Note that any sentinel value you might pick is a legal matrix entry.

Examples. [[1,1,1],[1,0,1],[1,1,1]] gives [[1,0,1],[0,0,0],[1,0,1]] · [[0,1,2,0],[3,4,5,2],[1,3,1,5]] gives [[0,0,0,0],[0,4,5,0],[0,3,1,0]]

pch.exerciseTag pch.exerciseTitle

Editorial — approach, complexity, follow-ups

Start from the $O(m + n)$ solution and say it out loud — it is a perfectly good answer and shows you have a working baseline: collect zero rows and columns in two sets, then apply them.

To reach $O(1)$, store those flags in the matrix’s own first row and column. Two things make this delicate:

1. The borders are real data too. Before using them as storage, record whether they originally contained a zero. Two booleans, not one — and matrix[0][0] alone cannot represent both.
2. Order matters. Zero the interior first, then the borders. If you zero row 0 early, every column looks marked and the whole matrix goes to zero.

Time $O(m \cdot n)$. Space $O(1)$.

Why not use a sentinel value?

A tempting shortcut is to write some unlikely marker (say -10^9) into cells that should become zero, then convert markers to zeros at the end. The constraints say entries span the full 32-bit signed range, so every sentinel is a legal input value and the approach is wrong on adversarial input. Interviewers ask about this deliberately; the borders trick is the answer that survives it.

Follow-ups you should expect: “Do the $O(m+n)$ version first” — often what they actually want before optimising. “What if you may not modify the input at all?” — then $O(m+n)$ sets and a fresh output matrix. “Set rows and columns to 1 where you find a 1?” — same structure, but check whether the marker and target values now collide.

LeetCode problem set

Generated from the problem database, so each entry carries its sheet membership and reported companies. Tick them off as you go — progress is saved in this browser, and the Export button writes it to a file you can keep.

Two one-liners worth knowing

list(zip(*matrix)) transposes any matrix, and [list(row) for row in zip(*matrix[::-1])] rotates 90° clockwise. They are elegant and correct — but they allocate, so they do not satisfy LC 48’s in-place requirement. Mention them to show fluency, then write the in-place version because that is what was asked.

9 problems

2 easy7 medium0 hard

Work down the ladder. Tick each problem off as you go — progress is saved in this browser, and the Export button in the filter bar writes it to a file you can keep.

AllEasyMediumHard

Unsolved onlyExportImportReset

• ○766Toeplitz MatrixeasyEvery cell equals its up-left neighbour; one comparison per cell
• ○867Transpose MatrixeasyNon-square, so you must allocate -- `zip(*matrix)` does it in one line
• ○36Valid SudokumediumNeetCode 150LeetCode Top Interview 150
• ○48Rotate ImagemediumTranspose then reverse rows; inner loop from `i + 1`NeetCode 150Blind 75LeetCode Top Interview 150
• ○54Spiral MatrixmediumFour boundaries and the two degenerate-case guardsNeetCode 150Blind 75LeetCode Top Interview 150
• ○59Spiral Matrix IImediumThe same walk, writing `1..n²` instead of reading
• ○73Set Matrix ZeroesmediumBorders as marker storage; no sentinel value is safeNeetCode 150Blind 75LeetCode Top Interview 150
• ○289Game of LifemediumSimultaneous update -- encode old and new state in two bitsLeetCode Top Interview 150
• ○498Diagonal TraversemediumCells on a diagonal share `r + c`; reverse alternate diagonals

Dry run

Rotate 90° clockwise, in place (LC 48) — transpose, then reverse each row.

Start:

1	2	3
4	5	6
7	8	9

After transposing (swap across the main diagonal, i < j only):

1	4	7
2	5	8
3	6	9

After reversing each row — the answer:

7	4	1
8	5	2
9	6	3

Two details worth saying out loud:

• The transpose loop must be for j in range(i + 1, n), not range(n). Iterating the full row swaps every pair twice and returns the original matrix. This is the most common way LC 48 fails.
• Anticlockwise is reverse-then-transpose, or transpose-then-reverse the columns. Derive it rather than memorising both — the two operations compose, and knowing that is more useful than either recipe.

Set Matrix Zeroes: the first row and column are markers, so handle them last

The $O(1)$-space trick for LC 73 stores “this row/column must be cleared” in the matrix’s own first row and column. But those cells are also data, so they must be recorded separately and written after everything else — otherwise a marker gets zeroed and then read back as a flag. Processing them first is the bug.

Interview follow-ups

They ask	What they’re checking	The answer
“Why does transpose + reverse equal a rotation?”	Whether you can justify it	Transpose maps (r,c) to (c,r); reversing rows then maps that to (c, n-1-r), which is the clockwise rotation
“Rotate counter-clockwise / 180°?”	Whether you memorised or understood	Transpose + reverse row order; or reverse rows and row order with no transpose
“Can you avoid the extra sets in LC 73?”	Space optimisation	Store the flags in row 0 and column 0, with two booleans for the borders themselves
“Why not a sentinel value?”	Reading the constraints	Entries span the full int range, so every sentinel is a possible real value
“Non-square rotation?”	Boundary thinking	Dimensions swap, so in-place is impossible; allocate the result
”$O(1)$ space with neighbour-based updates?”	Bit tricks	Encode next state in higher bits (LC 289), then shift in a second pass
“How do you avoid off-by-one in the spiral?”	Method, not luck	Name the four boundaries, shrink after each walk, and test single-row and single-column inputs

Edge-case checklist

• 1×1 matrix — every pattern must survive it.
• Single row [[1,2,3]] and single column [[1],[2],[3]] — the spiral guards exist for these; test both, always.
• Empty matrix [] or [[]] — guard before reading matrix[0].
• Non-square — fine for spiral and transpose, impossible for in-place rotation.
• A zero in row 0 or column 0 (LC 73) — the case the two booleans exist for.
• All zeros / no zeros (LC 73) — the trivial ends of the range.
• Even vs odd n (LC 48) — an odd n has a fixed centre cell; make sure your loop bounds neither skip nor double-swap it.
• Duplicate values — never identify a cell by its value; use indices.

Self-check

pch.quizTag Matrix and grid manipulation — self-check

1. In the in-place transpose, why must the inner loop start at i + 1?

   A To skip the diagonal, which never moves B Because iterating the full row swaps every pair twice, returning the original matrix C For speed D To avoid an index error
   pch.quizShowAnswer

   B — Because iterating the full row swaps every pair twice, returning the original matrix — Both halves of the swap get executed, undoing each other. The result is the input, unchanged — a silent failure that looks like the code did nothing.

2. In grid BFS, when should a cell be marked visited?

   A When it is dequeued B When it is enqueued — otherwise the same cell can enter the queue several times C After all its neighbours are processed D It does not matter
   pch.quizShowAnswer

   B — When it is enqueued — otherwise the same cell can enter the queue several times — A cell reachable from two neighbours gets queued twice if marking waits for the dequeue. The queue can grow far beyond O(rc) and the traversal degrades badly.

3. For Set Matrix Zeroes in O(1) space, the first row and column store the flags. What is the ordering trap?

   A The flags must be written before reading any data B The first row and column are also data, so their own zeroing must happen LAST — otherwise a marker is overwritten and then misread C The matrix must be square D There is no trap
   pch.quizShowAnswer

   B — The first row and column are also data, so their own zeroing must happen LAST — otherwise a marker is overwritten and then misread — Record separately whether row 0 and column 0 themselves need clearing, process the interior using them as flags, then clear them at the very end. Doing them first destroys the flags mid-pass.

4. Why is "a grid is a graph" the most useful observation in this phase?

   A It is a mnemonic with no practical use B Because islands, flood fill, rotting oranges and maze shortest-path are connected components, DFS, multi-source BFS and BFS — algorithms already known from the graph phase C Because grids can be converted to adjacency lists D Because it makes the code shorter
   pch.quizShowAnswer

   B — Because islands, flood fill, rotting oranges and maze shortest-path are connected components, DFS, multi-source BFS and BFS — algorithms already known from the graph phase — The 2-D shape is a costume. Naming the underlying algorithm turns an unfamiliar problem into one already solved, and it is the single highest-leverage recognition in this family.

5. How do you rotate a matrix 90 degrees ANTICLOCKWISE in place?

   A Transpose, then reverse each row (the same as clockwise) B Reverse the rows first, then transpose — or transpose then reverse each column C Rotate clockwise three times D It cannot be done in place
   pch.quizShowAnswer

   B — Reverse the rows first, then transpose — or transpose then reverse each column — The two operations compose, so derive the anticlockwise version rather than memorising it. Three clockwise rotations also work and is a fine answer to state, but it does three times the work.

Recall card

• Cue — a 2-D grid. First ask: is this traversal (then it is a graph problem) or transformation (then it is index arithmetic)?
• Rotate 90° clockwise — transpose with j from i + 1, then reverse each row. Anticlockwise is reverse-then-transpose.
• Traversal — 4 or 8 directions from a fixed DIRS list; mark visited on enqueue; bounds-check before dereferencing.
• Complexity — $O(rc)$ time. Space is $O(1)$ for transformations and $O(rc)$ for traversals.
• Remember — range(i + 1, n) in the transpose; markers in row 0 and column 0 must be resolved last; a grid is a graph.

Recap

• Rotation in place = transpose, then reverse each row. Inner loop from i + 1, or you swap everything twice and achieve nothing.
• Spiral traversal = four boundaries, shrink after each walk, and two guards so a lone remaining row or column is not walked twice.
• $O(1)$ space for row/column flags = store them in row 0 and column 0, keep two booleans for the borders, and write the borders last.
• When updates depend on neighbours’ original values, either use two passes or encode both states in one cell.
• No sentinel value is safe when the constraints allow the full integer range.
• Rearranging a grid is this page; searching a grid is BFS/DFS on grids.

Next: Monotonic Stack — the pattern behind next-greater-element and largest-rectangle problems.