Matrices

Rotation, spiral order, in-place state tricks and searching sorted matrices.

Matrix problems (rotate, spiral, set zeroes, game of life) rarely need a clever algorithm. They test careful index handling and, often, doing the work in place with O(1) extra space. A few reusable tricks cover nearly all of them.

Index basics

An m × n grid: rows, cols = len(grid), len(grid[0]). Check for empty input first.
Direction vectors keep neighbor loops short and bug-free:

DIRS4 = [(1, 0), (-1, 0), (0, 1), (0, -1)]
DIRS8 = DIRS4 + [(1, 1), (1, -1), (-1, 1), (-1, -1)]

def neighbors(r, c, rows, cols, dirs=DIRS4):
    for dr, dc in dirs:
        nr, nc = r + dr, c + dc
        if 0 <= nr < rows and 0 <= nc < cols:
            yield nr, nc

Flattening: cell (r, c) ↔ index r * cols + c. This is useful for union-find, and for binary search over a sorted matrix whose rows continue one into the next.
Diagonals: every cell on one diagonal has the same r - c, and every cell on one anti-diagonal has the same r + c. That's the key to diagonal traversal, Toeplitz checks and the N-Queens problem.

Rotate 90° clockwise in place

Rotation = transpose, then reverse each row. Two simple passes, instead of four-way swaps that are easy to get wrong.

def rotate(matrix):
    n = len(matrix)
    for i in range(n):
        for j in range(i + 1, n):                 # transpose: swap across the diagonal
            matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
    for row in matrix:
        row.reverse()                             # counter-clockwise: reverse the columns instead

Spiral order: shrinking boundaries

Keep four boundaries and shrink them after walking each side. Re-check the boundaries before the bottom and left sides, so single rows and single columns aren't counted twice.

def spiral_order(matrix):
    out = []
    top, bottom, left, right = 0, len(matrix) - 1, 0, len(matrix[0]) - 1
    while top <= bottom and left <= right:
        out += [matrix[top][c] for c in range(left, right + 1)]
        top += 1
        out += [matrix[r][right] for r in range(top, bottom + 1)]
        right -= 1
        if top <= bottom:
            out += [matrix[bottom][c] for c in range(right, left - 1, -1)]
            bottom -= 1
        if left <= right:
            out += [matrix[r][left] for r in range(bottom, top - 1, -1)]
            left += 1
    return out

Encoding extra state in place

When you have to update cells based on their old values without a copy:

Set matrix zeroes: use the first row and first column as markers for which rows and columns to clear, plus two flags for whether the first row or column itself contained a zero.
Game of life: encode both the old and new state in each cell, for example with bits. Bit 0 is the current state, bit 1 the next state. Shift everything right at the end.

def game_of_life(board):
    rows, cols = len(board), len(board[0])
    for r in range(rows):
        for c in range(cols):
            live = sum(board[nr][nc] & 1 for nr, nc in neighbors(r, c, rows, cols, DIRS8))
            if board[r][c] & 1 and live in (2, 3) or not board[r][c] & 1 and live == 3:
                board[r][c] |= 2                  # alive in the next generation
    for r in range(rows):
        for c in range(cols):
            board[r][c] >>= 1

Searching sorted matrices

In-place vs. a copy

Always ask: "Can I modify the input?" A copy makes the code simpler and is often fine. If the interviewer wants O(1) extra space, that's when the encoding tricks above come in.

[!WARNING] Rows vs. columns Most matrix bugs come from swapping rows and cols in a non-square grid. Test with a 2 × 3 matrix, not only a square one.

[!TIP] Practice Rotate Image · Spiral Matrix · Spiral Matrix II · Set Matrix Zeroes · Game of Life · Diagonal Traverse · Toeplitz Matrix · Valid Sudoku · Search a 2D Matrix II · Kth Smallest in a Sorted Matrix