Grids & Matrices

Grid problems usually combine movement constraints with reusable state. Decide whether to scan every cell, follow a constrained path, or preprocess regions for repeated queries.

1. Coordinates and Safe Access

Use (r,c) consistently and establish that the grid is rectangular. Handle empty input before reading its first row.

Build and copy grids safely

In Python, create independent rows with [[0] * C for _ in range(R)] and copy with [row.copy() for row in grid]. Avoid [[0] * C] * R: every row aliases the same list.

Validate before reading

Keep bounds and problem-specific rules in one helper. The bounds check must come first so the cell access cannot go out of range.

def is_valid(grid, r, c, blocked):
    if not grid:
        return False
    R, C = len(grid), len(grid[0])
    return (
        0 <= r < R
        and 0 <= c < C
        and grid[r][c] != blocked
    )

2. Moving Through a Grid

A directions array turns repeated row/column arithmetic into data:

• Four neighbors: (-1, 0), (1, 0), (0, -1), (0, 1).
• Add four diagonals for eight-way movement.
• Knight moves use eight (±2, ±1) / (±1, ±2) offsets.
• Sliding pieces or rays keep applying the same offset until blocked.

directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]

for dr, dc in directions:
    nr, nc = r + dr, c + dc
    if is_valid(grid, nr, nc, blocked):
        visit(nr, nc)

Iterating over a fixed directions list is $O(1)$ per cell. A full DFS or BFS is usually $O(RC)$ because each cell is visited at most once. Mark cells as visited when they are discovered so they are not queued or explored repeatedly.

3. Tracing Movement Patterns

Some questions are about pointer motion rather than graph search. Track the complete state—usually (r, c, direction)—and write down exactly when it changes.

Spirals and turns

For a spiral, move forward while the next cell is valid and unused; otherwise rotate the direction. With four directions, direction = (direction + 1) % 4 handles wraparound cleanly. Sometimes reversing the construction makes the starting point and turn rule much simpler.

Follow the constrained path

Do not scan all $RC$ cells when the input guarantees a narrow path. If each column contains one footprint and the next footprint can only be one row up, level, or one row down, find the starting row once and test only those three candidates in each next column. That improves $O(RC)$ to $O(R + C)$.

Let dependencies choose the scan order

Use row-major order for ordinary scans, reverse order when a cell depends on values below or to the right, and layer-by-layer order for BFS. The correct traversal is the one that makes required information available when you need it.

4. Subgrids and Reusing Work

A subgrid is a rectangular region inside the grid. Keep its boundaries explicit: top-left (r1, c1), bottom-right (r2, c2).

Validate a partially filled 9×9 board

A common interview task is to determine whether a partially filled board is currently valid—not to solve it. Each cell is empty or contains a digit from 1 to 9. Ignore empty cells. Every filled value must appear at most once in:

• Its row.
• Its column.
• Its 3×3 block.

Scan each filled cell (r, c) and track seen values for its row, column, and block. The block is identified by (r // 3, c // 3). If the value already exists in any corresponding set, the board is invalid.

Answer bottom-right region queries once

Suppose a query starts at (r, c) and asks about the complete rectangle from that cell to the grid's bottom-right corner. Rescanning that rectangle for every possible starting cell repeats the same work. Instead, build one output table whose cell (r, c) stores the answer for that rectangle.

Fill the output table from bottom-right to top-left. Start at (R - 1, C - 1), sweep right-to-left across each row, then move up one row. That order guarantees the smaller regions below and to the right are already available before they are referenced.

Suffix maximum

M[r][c] stores the largest input value in the rectangle from (r, c) to the bottom-right. Its recurrence reads the cell below and the cell to the right, so compute those cells first with the bottom-right-to-top-left order:

M[r][c] = max(grid[r][c], M[r + 1][c], M[r][c + 1])

Suffix sum

S[r][c] stores the sum of all input values in that same rectangle. Compute from bottom-right to top-left so the regions below and to the right are ready. Those regions overlap at (r + 1, c + 1), so subtract that overlap once:

S[r][c] = grid[r][c] + S[r + 1][c] + S[r][c + 1] - S[r + 1][c + 1]

Each output table takes $O(RC)$ time and space to build. Afterward, any bottom-right maximum or sum query is a single table lookup.

5. Matrix Transformations

You do not need advanced linear algebra for general interviews, but you should know the basic transformations:

• Transpose: swap matrix[r][c] with matrix[c][r]. For an in-place square transpose, visit only one side of the main diagonal so each pair is swapped once.
• Horizontal reflection: reverse every row.
• Vertical reflection: reverse the order of the rows.
• Clockwise rotation: transpose, then reflect horizontally.
• Counterclockwise rotation: transpose, then reflect vertically.

For addition and subtraction, matrices need matching dimensions and combine cell by cell. For multiplication, A shaped R x K times B shaped K x C produces R x C; each output cell is a row/column dot product. The order matters, and the direct algorithm takes $O(RKC)$ time.

Empty boundaries and negative values

Before reading grid[0], handle an empty grid or empty first row and establish that rows are rectangular. For suffix sums, a zero sentinel row and column remove edge branches. For suffix maximums, use -inf for missing neighbors, not zero: an all-negative region still has a negative maximum.

For arbitrary rectangular sum queries, use a 2D prefix table and inclusion-exclusion; the Prefix Sums guide gives the four-corner formula. For shortest grid distances or simultaneous spread, continue to Graphs and initialize all sources in one BFS. For path-dependent revisits, use Backtracking instead of a permanent global visited set.

Interview Checklist

Before coding, answer these questions:

1. What are R and C, and can the grid be empty?
2. Which moves are allowed: four-way, diagonal, jumps, or rays?
3. What makes a cell invalid: bounds, obstacles, visited state, or value?
4. Should the input be mutated, copied, or left unchanged?
5. What traversal order makes dependencies available?
6. Can a structural guarantee let you trace only part of the grid?
7. Is the expected complexity $O(RC)$, or can preprocessing answer repeated region queries faster?