L50 · Matrix Manipulation

Series: LeetCode — From Basics to Interview-Ready · Session 50 / 65 · Phase 3 · Advanced & specialised

Why this session exists

Rotate equals transpose plus reverse. It is elegant, it is memorable, and it does genuinely land well in an interview — not because it is difficult, but because the alternative shows the candidate did not look for structure. Most people attempt the four-way cyclic swap, get lost in the index arithmetic, and burn eight minutes producing something they cannot verify. Two lines of decomposition avoids all of it.

The broader lesson is that matrix problems are almost never about clever algorithms. They are about index discipline. There is no asymptotic insight to find in Rotate Image or Spiral Matrix — you must touch every cell, so O(m·n) is the floor and every reasonable solution achieves it. What separates solutions is whether the index arithmetic is correct and whether you can convince yourself of that under time pressure.

So this session is about techniques that make index arithmetic tractable. Decompose a hard transformation into two easy ones. Maintain explicit named boundaries rather than deriving positions from a loop counter. Reuse the matrix itself as scratch space when the problem demands O(1) extra memory.

Set Matrix Zeroes is the one with actual depth. The naive solution uses O(m + n) marker arrays and is fine. The O(1) solution stores those markers in the first row and first column of the matrix itself, which means the markers and the data occupy the same memory and you must be extremely careful about the order in which you read and write. That ordering constraint is a real idea and it generalises.

Blank-file warm-up

Five minutes, empty file, no notes. Write in-place transpose:

1. The double loop, with the correct inner bound.
2. The swap.
3. Then the row reversal that completes the 90-degree clockwise rotation.

The inner bound is the thing. for j in range(i + 1, n) — starting at i + 1, not at 0. Starting at 0 swaps every pair twice and returns the matrix to its original state, which is a bug that produces no error and no visible change.

Pattern anatomy

The shape that summons this pattern: a 2D grid where the answer is a rearrangement or traversal of the grid itself, usually with an in-place or O(1)-space requirement.

There is no single invariant across the family. There are three techniques, each with its own.

Rotation by decomposition. The invariant is algebraic: rotating 90 degrees clockwise maps cell (i, j) to (j, n-1-i). Transposing maps (i, j) to (j, i). Reversing each row maps (i, j) to (i, n-1-j). Compose transpose then row-reverse and you get (i, j) → (j, i) → (j, n-1-i), which is exactly the rotation. That composition is the proof, and it fits in one line.

def rotate(matrix):
    """90 degrees clockwise, in place."""
    n = len(matrix)
    for i in range(n):
        for j in range(i + 1, n):              # upper triangle ONLY
            matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
    for row in matrix:
        row.reverse()

For counter-clockwise, transpose then reverse the columns — or equivalently reverse the rows of the matrix first, then transpose. Derive it the same way rather than memorising a second recipe.

Spiral by boundary shrinking. The invariant is that four variables top, bottom, left, right always delimit the unvisited rectangle. Each of the four directional sweeps consumes one edge and moves one boundary inward.

def spiral_order(matrix):
    if not matrix:
        return []
    out = []
    top, bottom = 0, len(matrix) - 1
    left, right = 0, len(matrix[0]) - 1
 
    while top <= bottom and left <= right:
        for j in range(left, right + 1):       # left to right along the top
            out.append(matrix[top][j])
        top += 1
 
        for i in range(top, bottom + 1):       # top to bottom along the right
            out.append(matrix[i][right])
        right -= 1
 
        if top <= bottom:                      # guard: rows may be exhausted
            for j in range(right, left - 1, -1):
                out.append(matrix[bottom][j])
            bottom -= 1
 
        if left <= right:                      # guard: columns may be exhausted
            for i in range(bottom, top - 1, -1):
                out.append(matrix[i][left])
            left += 1
    return out

The two guards before the third and fourth sweeps are the entire difficulty of this problem. Without them, a single-row matrix gets its row emitted left-to-right by the first sweep and then again right-to-left by the third. Same for a single column.

First-row-and-column marking. The invariant is an ordering discipline: you write markers into row 0 and column 0, and then you must apply them in an order that does not destroy a marker before reading it.

def set_zeroes(matrix):
    rows, cols = len(matrix), len(matrix[0])
    first_row_zero = any(matrix[0][j] == 0 for j in range(cols))
    first_col_zero = any(matrix[i][0] == 0 for i in range(rows))
 
    for i in range(1, rows):                   # mark, skipping row 0 and col 0
        for j in range(1, cols):
            if matrix[i][j] == 0:
                matrix[i][0] = 0
                matrix[0][j] = 0
 
    for i in range(1, rows):                   # apply, still skipping them
        for j in range(1, cols):
            if matrix[i][0] == 0 or matrix[0][j] == 0:
                matrix[i][j] = 0
 
    if first_row_zero:                         # apply row 0 and col 0 LAST
        for j in range(cols):
            matrix[0][j] = 0
    if first_col_zero:
        for i in range(rows):
            matrix[i][0] = 0

Two separate boolean flags for row 0 and column 0 are necessary because matrix[0][0] would otherwise serve as the marker for both, and one would clobber the other.

The cue

You are looking at a matrix-manipulation problem when the statement contains these tells:

1. "In place" combined with a 2D input. This is a direct instruction to find a swap-based or marker-based technique rather than allocating a second grid.
2. "Rotate", "spiral", "transpose", "diagonal traversal", "zigzag". Direct vocabulary matches for the geometry family.
3. "O(1) extra space" on a grid problem. The matrix itself must become the scratch space, which usually means encoding markers in the first row and column, or encoding two states per cell using arithmetic.
4. A square constraint, n × n rather than m × n. Squareness enables transposition, which is only defined in place for square matrices.
5. The answer is a traversal order rather than a computed value. Spiral, diagonal, boustrophedon. These are all boundary-management problems.

Tell 3 is worth dwelling on. When a grid problem demands O(1) space, there are only a few places to hide information: the first row and column, the sign bit of values, or an encoding like new_value * k + old_value when the value range is bounded. Knowing that list turns "impossible" into "which one".

Guided solve

Rotate Image — rotate an n × n matrix 90 degrees clockwise, in place.

Begin by working out where a single cell must go, because everything follows from that. Take the top-left cell (0, 0). After a clockwise rotation it must be at the top-right, (0, n-1). Take (0, 1); it goes to (1, n-1). The general mapping is (i, j) → (j, n-1-i).

The direct approach is a four-cycle: cell (i, j) goes to (j, n-1-i), which goes to (n-1-i, n-1-j), which goes to (n-1-j, i), which returns to (i, j). Rotate those four values simultaneously, looping over one quadrant. It is correct and it is O(1) space, but you must get the loop bounds right for both even and odd n, and you must get four index expressions right with no way to check them except tracing. Under interview pressure this is where people lose time.

The better approach is decomposition. Ask: is (i, j) → (j, n-1-i) the composition of two operations I already know?

Transpose is (i, j) → (j, i). That is a reflection across the main diagonal, and it gets the first coordinate right.

Reverse each row is (i, j) → (i, n-1-j). That is a horizontal mirror.

Compose them: start at (i, j), transpose to (j, i), then reverse the row to (j, n-1-i). Exactly the rotation. So transpose, then reverse rows. Two operations, each of which is trivially verifiable on its own.

Now the transpose bound. Swapping matrix[i][j] with matrix[j][i] for all i and j swaps each pair twice — once when the loop is at (i, j) and again at (j, i) — restoring the original. You must iterate only the upper triangle, so j runs from i + 1 to n - 1. Diagonal cells where i == j are fixed points and need no swap.

Row reversal is row.reverse() in Python, or a two-pointer swap if the interviewer wants it explicit.

Trace on a 3×3 with values 1 through 9 in reading order. Transpose gives [[1,4,7],[2,5,8],[3,6,9]]. Reverse each row gives [[7,4,1],[8,5,2],[9,6,3]]. Check the corner: the original top-left 1 is now at top-right. Correct.

Solo timed

Fifteen minutes each, timer running, no editorial until it fires.

• Spiral Matrix — four boundaries. Do not forget the two guards before the bottom and left sweeps. Test with a single row, a single column, and a 1×1 before declaring it done.
• Set Matrix Zeroes — O(1) space using the first row and column as markers. The ordering of the apply phases is the whole problem; write down the order before coding.

If both land early, do Game of Life — the in-place version encodes both the old and new state in one cell using two bits, which is the third O(1)-space technique and a good one to have seen.

Common failure modes

Transposing the whole matrix instead of the upper triangle. Every pair swaps twice and the matrix is unchanged. Silent, and confusing precisely because there is no visible symptom.

Missing the guards in the spiral loop. A single-row matrix emits its row twice, once forward and once backward. Always test [[1,2,3]] and [[1],[2],[3]].

Using matrix[0][0] as a marker for both the first row and the first column. It cannot serve both. You need one extra boolean for one of them, and the standard choice is two booleans for clarity.

Applying the first-row and first-column zeroes before the interior. The markers live there. Zero them first and every marker is destroyed, and the entire matrix ends up zeroed. Interior first, boundaries last — write the order down.

Assuming the matrix is square when it is m × n. In-place transpose is undefined for non-square matrices. Rotation problems specify square; spiral and zeroes problems generally do not.

Off-by-one in the reverse-direction sweeps. range(right, left - 1, -1) needs the - 1 because range is exclusive at the stop. Writing range(right, left, -1) silently drops the leftmost element of every bottom sweep.

Complexity

Rotate Image: O(n²) time, O(1) space. Transposition touches roughly n²/2 cells and row reversal touches all n², so it is about 1.5n² operations against the four-cycle's n². Both are O(n²), and there is no faster option since every cell must move.

Spiral Matrix: O(m·n) time, O(1) extra space beyond the output list, which is required by the problem and therefore does not count. Every cell is appended exactly once, and the four boundaries guarantee no cell is visited twice.

Set Matrix Zeroes: O(m·n) time. Three passes — mark, apply interior, apply boundaries — each linear in the cell count. O(1) space with the first-row-and-column technique, versus O(m + n) with separate marker arrays. Note that O(m + n) is already tiny relative to the O(m·n) input, so the optimisation is more about demonstrating the technique than about real memory savings.

The floor for all of these is O(m·n) because the output depends on every input cell. There is no clever asymptotic win available in this family, and recognising that quickly is itself useful — it means you should spend your thinking on correctness rather than on searching for a faster approach that does not exist.

Spaced queue

Re-solve whatever is due before starting anything new today. Status ladder:

• cold — solved unaided, first attempt clean → next review in 60 days
• warm — solved but slowly or with a stumble → 21 days
• hint — needed a nudge to get started → 7 days
• failed — could not produce a working solution → 2 days, then 7 days

Matrix problems decay unusually fast because the knowledge is index arithmetic rather than a concept, and index arithmetic has nothing to hang on. Expect to re-review these more often than the pattern-based sessions.