Matrix

How it works

A matrix problem is an array problem with two coordinates. Most of the difficulty is bookkeeping: staying inside the bounds, visiting cells in the right order, and not overwriting a value you still need.

Keep a direction list such as [(0, 1), (1, 0), (0, -1), (-1, 0)] and loop over it instead of writing four near-identical blocks. Pair it with a single in-bounds check. Spiral traversals cycle through the same list, turning when they hit a boundary.

In-place transformations rely on decomposing the operation. A 90-degree clockwise rotation is a transpose followed by reversing each row. Setting rows and columns to zero in O(1) extra space uses the first row and first column as marker storage.

When cells are nodes and neighbors are edges, the matrix is a graph: flood fill, islands and shortest paths through a maze are graph traversals. Sorted matrices add a search angle: starting from the top-right corner, each comparison eliminates a row or a column.

How to attack it

1. 1Write rows and cols once and a single in-bounds helper.
2. 2Use a direction list instead of repeated neighbor code.
3. 3Decide whether you need a copy or can transform in place, and in which order.
4. 4Treat cells as graph nodes when the question is about connectivity or distance.
5. 5Test with 1 × 1, a single row, a single column, and a non-square matrix.

Template

A skeleton to adapt, not a solution to paste. Write it from memory a few times.

DIRS = [(0, 1), (1, 0), (0, -1), (-1, 0)]   # right, down, left, up


def spiral(matrix):
    if not matrix:
        return []
    rows, cols = len(matrix), len(matrix[0])
    seen = [[False] * cols for _ in range(rows)]
    r = c = d = 0
    out = []
    for _ in range(rows * cols):
        out.append(matrix[r][c])
        seen[r][c] = True
        nr, nc = r + DIRS[d][0], c + DIRS[d][1]
        if not (0 <= nr < rows and 0 <= nc < cols) or seen[nr][nc]:
            d = (d + 1) % 4                      # turn clockwise
            nr, nc = r + DIRS[d][0], c + DIRS[d][1]
        r, c = nr, nc
    return out


def rotate_clockwise(m):
    # In place for a square matrix: transpose, then reverse each row.
    n = len(m)
    for i in range(n):
        for j in range(i + 1, n):
            m[i][j], m[j][i] = m[j][i], m[i][j]
    for row in m:
        row.reverse()

What it costs