Matrices — How the Pattern Works
Matrix traversal and manipulation patterns solve 2D grid problems by pairing deliberate cell-visiting orders—row-major, concentric boundary rings, zigzag anti-diagonals, monotonic staircases, or BFS/Dijkstra frontiers—with coordinate invariants and in-place state encoding. Maintaining structural invariants such as shrinking ring bounds [top, bottom, left, right], monotonic column pointers on doubly sorted grids, or composite cell codes that preserve previous states alongside next states eliminates auxiliary O(m * n) grid copies and reduces brute-force O(m * n) or exponential searches to O(m + n), O(m log(m * n)), or single-pass O(m * n) algorithms.
- The input is an m x n 2D grid requiring non-trivial traversal geometry such as concentric clockwise spirals, alternating diagonals, 90-degree in-place rotations, matrix transposition, or 1D-to-2D index reshaping.
- Constraints demand O(1) auxiliary space while modifying rows, columns, or simultaneous multi-cell generations that would otherwise cascade or overwrite unread neighbor states.
- Rows and columns exhibit monotonic ordering (explicitly sorted grids or implicit products r * c), enabling O(m + n) staircase elimination from a saddle corner or binary search over the value range.
- Cells interact through 4-directional or 8-directional adjacency—counting exposed perimeters, bounding connected components, racing multi-source hazard BFS fronts, or minimizing path bottleneck elevations with a min-heap.
- Grid operations apply uniformly across an axis or decompose additively by coordinate, allowing row canonicalization via hash maps or decoupling 2D Manhattan distances into independent 1D medians.
- Re-reading degenerate inner strips in Spiral Matrix: when m != n and a single row (top == bottom) or single column (left == right) remains after advancing top and right, omitting the if top <= bottom and if left <= right guards traverses that final strip a second time in reverse.
- Double-swapping across the main diagonal during in-place transpose: starting the column loop at c = 0 instead of c = r + 1 swaps (r, c) with (c, r) twice and leaves the matrix unchanged.
- Overwriting margin markers or unread states prematurely: clearing row 0 or column 0 before finishing the inner subgrid in Set Matrix Zeroes destroys column/row markers, and writing final 0/1 values mid-pass in Game of Life corrupts neighbor counts for subsequent cells.
- Checking non-corner bounds first in Diagonal Traverse: at the top-right corner (0, n - 1) while moving up-right, testing r < 0 (slide right to c + 1) before testing c == n - 1 (slide down to r + 1) pushes the column index out of bounds.
top, bottom, left, right = 0, len(mat) - 1, 0, len(mat[0]) - 1
while top <= bottom and left <= right:
for c in range(left, right + 1): visit(mat[top][c])
top += 1
for r in range(top, bottom + 1): visit(mat[r][right])
right -= 1
if top <= bottom:
for c in range(right, left - 1, -1): visit(mat[bottom][c])
bottom -= 1
if left <= right:
for r in range(bottom, top - 1, -1): visit(mat[r][left])
left += 1def rotate_clockwise(mat):
n = len(mat)
for r in range(n):
for c in range(r + 1, n):
mat[r][c], mat[c][r] = mat[c][r], mat[r][c]
for row in mat:
row.reverse()def staircase_count(grid):
n = len(grid[0])
c, total = n, 0
for row in grid:
while c > 0 and row[c - 1] < 0:
c -= 1
total += n - c
return totaldef simultaneous_update(board):
m, n = len(board), len(board[0])
for r in range(m):
for c in range(n):
prev = count_neighbors_in_states(board, r, c, (1, 2))
if board[r][c] == 1 and dies(prev):
board[r][c] = 2 # was 1, becomes 0
elif board[r][c] == 0 and born(prev):
board[r][c] = 3 # was 0, becomes 1
for r in range(m):
for c in range(n):
board[r][c] %= 2