Matrix Manipulation

Review boundary and corrected contracts

Clockwise rotation is transpose followed by reversing rows, mapping (i,j)→(j,n−1−i), for square matrices. Spiral traversal keeps an unvisited rectangle and guards exhausted dimensions. Zero marking must preserve first-row and first-column flags until the end. The code uses rectangular Python lists with distinct row objects; rotation requires square shape and set_zeroes requires at least one row and one column. Spiral traversal also returns [] for an empty matrix or zero-width rectangular rows. Ragged and aliased rows are outside these contracts.

The examples below teach the stated input contracts; fragments and deliberately incorrect counterexamples are exercises, not production implementations. Complexity counts elementary operations unless a bit-cost or allocation caveat is stated. Practice times are suggestions, not measured performance or hiring guarantees.

Learning objective: Learn three in-place matrix techniques cold: transpose-then-reverse for rotation, four-boundary shrinking for spiral order, and first-row-and-column marking for O(1) space.

Series: LeetCode — From Basics to Production-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 under a tight review — not because it is difficult, but because the alternative shows the engineer 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 order of the rows (matrix.reverse()), or reverse each row first and then transpose. Reversing the row order before transposing instead gives clockwise rotation. 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 can revisit all but its rightmost cell on the third sweep. Similarly, a sufficiently long single column can revisit cells on the fourth sweep.

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

This implementation uses two boolean flags for clarity: matrix[0][0] cannot independently encode both original boundary-zero conditions. A different traversal can let that cell represent one boundary and use a single external flag for 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 this symmetric-swap transpose without changing the nested-list shape. Rectangular transposition is mathematically defined but changes dimensions and needs a different storage algorithm.
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 design review 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 a reviewer 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.

Counter-clockwise: transpose, then reverse the columns — meaning reverse the order of the rows themselves, matrix.reverse(). Do not memorise this as a separate recipe. Derive it: counter-clockwise is (i, j) → (n-1-j, i), and transposing gives (j, i), so you need (j, i) → (n-1-j, i), which is a vertical flip. Deriving takes twenty seconds and never fails; memorising two similar recipes leads to picking the wrong one.

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 can duplicate cells from the already-visited row on the bottom sweep. 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. Clearing an originally zero-containing boundary too early can introduce false markers and zero unrelated interior cells. Interior first, boundaries last — write the order down.

Assuming the matrix is square when it is m × n. This symmetric-swap implementation does not transpose a non-square nested list correctly; rectangular transpose changes the shape. 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.

Myth: Rotating a matrix in place requires the four-way cyclic swap, since transposing and then reversing touches every element twice and must therefore be slower.

Why: Both approaches take Θ(n²) time for an arbitrary square matrix, but that does not establish a wall-clock ratio. A four-cycle writes each moved cell once, while transpose plus row reversal performs two simpler phases. The decomposition gives inspectable intermediate states; choose between them for clarity or measured performance, not an unmeasured “less than 2x” claim.

Steps 1: Because a 90-degree clockwise rotation is a rigid transformation of positions, it can be written as a single index mapping: (i, j) goes to (j, n-1-i).

Steps 2: Because transposition is the mapping (i, j) to (j, i), it accounts for the coordinate exchange but leaves the second index unreflected.

Steps 3: Because reversing each row is the mapping (i, j) to (i, n-1-j), applying it after transposition produces (j, n-1-i), which is exactly the rotation.

Steps 4: Because each of those two operations is its own simple loop with one index expression, correctness can be verified independently for each step.

Steps 5: Because both operations run over O(n^2) cells with constant work, the composition is O(n^2), the same as any correct rotation.

Steps 6: Therefore the testable prediction is that composing the two operations gives identical output to the four-cycle swap on every input — verify by generating random matrices and comparing element by element.

Picture: You are not turning the picture. You are flipping the paper over along its diagonal crease, then flipping it left to right. Two flips of a flat sheet compose into a quarter turn, which is why the rotation never needs to be performed as a rotation.

Trigger: Fires when a grid transformation has an awkward index formula — ask whether it factors into two reflections you already know.

Name: Transpose then reverse

Gain: Two independently verifiable steps; four short lines; each step is a one-line index expression you can reason about alone; demonstrates that you looked for structure

Cost: Two phases and generally more cell writes than a four-cycle; the displayed shape-preserving swap code requires a square matrix.

Name: Four-way cyclic swap

Gain: Each moved cell is written once; an odd-sized matrix has a fixed central cell that need not be written.

Cost: Four index expressions to get right simultaneously; quadrant bounds differ for even and odd n; no intermediate state to inspect when it is wrong

Pick: Prefer transpose-then-reverse when its two simple proofs make the implementation easier to verify. A four-cycle is also correct; measure actual performance if write traffic matters, and test even and odd sizes.

Complexity

Rotate Image: Θ(n²) time, O(1) auxiliary space. There are n(n−1)/2 transpose swaps and n·floor(n/2) row-reversal swaps. Counting each swap as two cell writes gives their write count, not elapsed time. A four-cycle moves n² cells for even n and n²−1 for odd n. The central cell of an odd square is fixed; arbitrary remaining values still require quadratic work.

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.

Quiz

Self-check (answer follows each question).

Q: Why must the transpose loop use for j in range(i + 1, n) rather than starting j at 0?

A: Starting at 0 visits each pair twice — once as (i, j) and once as (j, i) — so each swap is undone and the matrix is unchanged. Only the upper triangle should be swapped.

Q: Derive the counter-clockwise rotation from the clockwise one.

A: Counter-clockwise maps (i, j) to (n-1-j, i). Transposing gives (j, i), so the remaining step must take (j, i) to (n-1-j, i), which is a vertical flip — reverse the order of the rows. So: transpose, then reverse the row order.

Q: Why does the spiral loop need guards before the bottom and left sweeps but not before the top and right ones?

A: The while condition guarantees a nonempty rectangle for the top sweep. After top increments, the right sweep needs no separate row guard because range(top, bottom+1) is empty if no rows remain. The bottom and left sweeps need their guards to avoid revisiting an exhausted row or column. Removing both guards on [[1,2,3]] produces [1,2,3,2,1], not a valid traversal.

Q: In Set Matrix Zeroes, why does this implementation use two separate boolean flags?

A: The flags preserve whether the original first row and first column contained a zero before those boundaries become marker storage. matrix[0][0] alone cannot hold two independent facts; this implementation stores both externally. A carefully ordered alternative can store one fact in that cell and use one external flag.

Q: What is the required ordering of the apply phases in Set Matrix Zeroes and why?

A: Interior cells first, then apply the saved boundary flags. Otherwise a newly cleared boundary can create false markers and zero unrelated interior cells. For [[0,1],[1,1]], clearing boundaries before reading markers incorrectly clears the bottom-right 1; correct output is [[0,0],[0,1]].

Q: Game of Life asks for an in-place update where every cell changes simultaneously. How do you store two states per cell in O(1) space?

A: Encode both old and new state in the same integer using two bits — for example keep the old state in bit 0 and write the new state into bit 1, then right-shift every cell by one in a final pass. Any encoding that makes the old value recoverable while the new one is being written works; the point is that a bounded value range leaves spare capacity.

Stretch: true

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.

• Rotate = transpose + reverse rows. Derive it from the index mapping rather than memorising it, so counter-clockwise costs you twenty seconds instead of a second recipe.

• Transpose only the upper triangle. Swapping the full matrix undoes itself and produces no visible symptom.

• Spiral traversal is four named boundaries shrinking inward, with guards before the third and fourth sweeps.

• O(1) space on a grid means hiding state in the matrix: the first row and column, spare bits, or arithmetic encoding.

• In Set Matrix Zeroes, apply the interior before the boundaries — the markers live in the boundaries.

• Every solution here is O(m*n) because every cell must be touched. Spend your effort on correctness, not on a faster approach that does not exist.

Corrective source notes

• 5. Data Structures — Python 3.14 documentation — list.reverse reverses a list in place. Rotation, spiral and marker proofs are derived here; the dictionary passage is not evidence for them. Checked 2026-10-07.

These citations support the named claims, not blanket certification of the lesson. Worked proofs are derived in the text; execution scope and finite-test limits are recorded separately.