Matrix2D arrays

01Why it exists

Reach for it when you see:Grid, two-dimensional, m × n, up/down/left/right, neighbours, rotation or transposition, spiral, board, image.

02The core idea

A two-dimensional array is just an array of arrays: grid[r][c] picks row r first, then cell c inside that row. By convention r is the row (the vertical axis) and c is the column (the horizontal axis), so m = len(grid) is the number of rows and n = len(grid[0]) is the number of columns. Getting r and c the wrong way round is the most common bug in this whole family of problems.

In memory it is really one-dimensional: the rows sit one after another (row-major), so grid[r][c] can equally be written as the flat flat[r × n + c]. Going the other way, flat index k corresponds to (k ÷ n, k mod n). That conversion is what turns "binary search over an m × n matrix" into an ordinary one-dimensional binary search.

Matrix problems come with three standard tools. A direction array: write the four (or eight) directions as a list of (dr, dc) pairs, and one loop covers every neighbour with the bounds check written exactly once. Shrinking bounds: spiral traversal moves top / bottom / left / right inwards, which is cleaner than keeping track of which way you are turning. In-place transforms: a rotation is a transpose plus a reversal, and marker information can borrow the first row and the first column, saving O(mn) of extra space.

03The algorithm

1. 1Pin down m, n and the index order first: grid[r][c], with 0 ≤ r < m and 0 ≤ c < n. An empty matrix needs its own special case.
2. 2To look at neighbours, use a direction array: for dr, dc in DIRS, work out (nr, nc), then run the bounds check before doing anything with the cell.
3. 3Spiral traversal: walk one side each going right, down, left and up, and shrink the matching bound inwards by one every time a side is finished. Before the left and up passes of each lap, check again that the bounds have not crossed, or a lone row or column will be visited twice.
4. 4Rotating 90° (clockwise): transpose by swapping each pair above the diagonal with swap(a[r][c], a[c][r]), then reverse every row. For anticlockwise, reverse every column top to bottom instead.
5. 5When you have to mark "this row" or "this column" and cannot allocate anything new, write the marks into the first row and the first column — but record separately, beforehand, whether those two were marked in their own right.

04Interactive demo

"Spiral traversal" shows the visit order cell by cell along with the way the four bounds close in; "Rotate 90°" steps through every swap of the transpose and then the reversal of each row.

05Code

Starting with building a matrix and the direction array, then spiral traversal, the in-place rotation, and Set Matrix Zeroes using the edge row and edge column as its markers.

# Build an m × n matrix. Never write [[0] * n] * m: that makes every row the same list
grid = [[0] * 4 for _ in range(3)]
m, n = len(grid), len(grid[0])       # number of rows, number of columns
grid[r][c]                           # row first, then column

# Moving in four directions: use a direction array, not four separate if branches
DIRS = [(0, 1), (1, 0), (0, -1), (-1, 0)]     # right, down, left, up

def neighbors(r, c):
    for dr, dc in DIRS:
        nr, nc = r + dr, c + dc
        if 0 <= nr < m and 0 <= nc < n:       # the bounds check lives in one place only
            yield nr, nc


# Spiral traversal (LeetCode 54): four bounds shrinking inwards
def spiral_order(matrix):
    out = []
    top, bottom = 0, len(matrix) - 1
    left, right = 0, len(matrix[0]) - 1
    while top <= bottom and left <= right:
        for c in range(left, right + 1):  out.append(matrix[top][c])
        top += 1
        for r in range(top, bottom + 1):  out.append(matrix[r][right])
        right -= 1
        if top <= bottom:
            for c in range(right, left - 1, -1): out.append(matrix[bottom][c])
            bottom -= 1
        if left <= right:
            for r in range(bottom, top - 1, -1): out.append(matrix[r][left])
            left += 1
    return out


# Rotate 90° clockwise in place (LeetCode 48): transpose, then reverse each row
def rotate(matrix):
    n = len(matrix)
    for r in range(n):
        for c in range(r + 1, n):                  # only swap above the diagonal
            matrix[r][c], matrix[c][r] = matrix[c][r], matrix[r][c]
    for row in matrix:
        row.reverse()


# Use the first row and the first column as markers, O(1) extra space (LeetCode 73)
def set_zeroes(matrix):
    m, n = len(matrix), len(matrix[0])
    first_row_zero = any(matrix[0][c] == 0 for c in range(n))
    first_col_zero = any(matrix[r][0] == 0 for r in range(m))
    for r in range(1, m):
        for c in range(1, n):
            if matrix[r][c] == 0:
                matrix[r][0] = matrix[0][c] = 0    # record it on the edges
    for r in range(1, m):
        for c in range(1, n):
            if matrix[r][0] == 0 or matrix[0][c] == 0:
                matrix[r][c] = 0
    if first_row_zero:
        for c in range(n): matrix[0][c] = 0
    if first_col_zero:
        for r in range(m): matrix[r][0] = 0

06Practice

• LeetCode 54Spiral MatrixMedium
• LeetCode 48Rotate ImageMedium
• LeetCode 73Set Matrix ZeroesMedium
• LeetCode 36Valid SudokuMedium
• LeetCode 74Search a 2D Matrix (treat the grid as one flat array and binary search it)Medium
• LeetCode 200Number of Islands (try a direction array plus DFS first)Medium