AdvancedData Structures & Algorithms · Lesson 21 of 25 · Updated ·
Matrix Traversal — Rows, Columns, Spiral, Diagonals and Grid Moves
A matrix (2D array) is a grid of R rows and C columns; m[r][c] is the cell in row r, column c. Matrix questions are everywhere in placement tests — spiral print, rotate image, search a sorted matrix, count islands — and they all come down to visiting cells in a particular order without going out of bounds.
1. Row by row and column by column
m = [[1, 2, 3],
[4, 5, 6]]
R, C = len(m), len(m[0])
for r in range(R): # row-major: the normal reading order
print(*[m[r][c] for c in range(C)])
cols = [[m[r][c] for r in range(R)] for c in range(C)] # column-major
print(cols)
print([sum(row) for row in m], [sum(col) for col in cols])
1 2 3
4 5 6
[[1, 4], [2, 5], [3, 6]]
[6, 15] [5, 7, 9]
R = len(m)is the number of rows;C = len(m[0])the number of columns.- Visiting every cell is always O(R × C).
2. Spiral order
Print the matrix going right → down → left → up, then move inward. Keep four borders — top, bottom, left, right — and shrink one after each side is printed.
def spiral(m):
out = []
top, bottom, left, right = 0, len(m) - 1, 0, len(m[0]) - 1
while top <= bottom and left <= right:
for c in range(left, right + 1): out.append(m[top][c])
top += 1
for r in range(top, bottom + 1): out.append(m[r][right])
right -= 1
if top <= bottom: # a row is still left
for c in range(right, left - 1, -1): out.append(m[bottom][c])
bottom -= 1
if left <= right: # a column is still left
for r in range(bottom, top - 1, -1): out.append(m[r][left])
left += 1
return out
print(spiral([[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12], [13, 14, 15, 16]]))
print(spiral([[1, 2, 3], [4, 5, 6]]))
[1, 2, 3, 4, 8, 12, 16, 15, 14, 13, 9, 5, 6, 7, 11, 10]
[1, 2, 3, 6, 5, 4]
The two if checks matter for non-square matrices: without them, a single remaining row or column gets printed twice.
3. Transpose and rotate by 90°
Transpose swaps rows and columns: t[c][r] = m[r][c]. Rotating a square matrix 90° clockwise in place = transpose, then reverse every row.
def rotate_clockwise(m):
n = len(m)
for r in range(n):
for c in range(r + 1, n): # only above the diagonal
m[r][c], m[c][r] = m[c][r], m[r][c]
for row in m:
row.reverse()
return m
for row in rotate_clockwise([[1, 2, 3], [4, 5, 6], [7, 8, 9]]):
print(row)
[7, 4, 1]
[8, 5, 2]
[9, 6, 3]
- The inner loop starts at
r + 1; starting at 0 would swap every pair twice and undo the transpose. - Anticlockwise: transpose, then reverse every column (or reverse the rows first, then transpose).
4. Diagonals
Cells on the same main diagonal have the same r − c; cells on the same anti-diagonal have the same r + c. That one fact solves diagonal sums, "is this a valid N-Queens board" and "print the matrix diagonally".
m = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
n = len(m)
print(sum(m[i][i] for i in range(n)), sum(m[i][n - 1 - i] for i in range(n)))
diag = {}
for r in range(n):
for c in range(n):
diag.setdefault(r + c, []).append(m[r][c])
print([diag[k] for k in sorted(diag)])
15 15
[[1], [2, 4], [3, 5, 7], [6, 8], [9]]
5. Moving to neighbours: direction arrays
Grid problems (islands, flood fill, shortest path in a maze, rotting oranges) move from a cell to its 4 neighbours. Write the moves once as two arrays instead of four copies of the same code.
Here is a breadth-first search that counts the steps from the top-left to the bottom-right corner of a maze (# = wall):
from collections import deque
def shortest_path(grid):
R, C = len(grid), len(grid[0])
dist = [[-1] * C for _ in range(R)]
dist[0][0] = 0
q = deque([(0, 0)])
while q:
r, c = q.popleft()
for dr, dc in ((-1, 0), (1, 0), (0, -1), (0, 1)):
nr, nc = r + dr, c + dc
if 0 <= nr < R and 0 <= nc < C and grid[nr][nc] == '.' and dist[nr][nc] == -1:
dist[nr][nc] = dist[r][c] + 1
q.append((nr, nc))
return dist[R - 1][C - 1]
maze = ["..#.",
".##.",
"....",
"#.#."]
print(shortest_path(maze))
6
For 8 directions (king moves, "count neighbours" in Game of Life), add the four diagonal moves (±1, ±1).
The same spiral in Java
import java.util.*;
public class Main {
static List<Integer> spiral(int[][] m) {
List<Integer> out = new ArrayList<>();
int top = 0, bottom = m.length - 1, left = 0, right = m[0].length - 1;
while (top <= bottom && left <= right) {
for (int c = left; c <= right; c++) out.add(m[top][c]);
top++;
for (int r = top; r <= bottom; r++) out.add(m[r][right]);
right--;
if (top <= bottom) { for (int c = right; c >= left; c--) out.add(m[bottom][c]); bottom--; }
if (left <= right) { for (int r = bottom; r >= top; r--) out.add(m[r][left]); left++; }
}
return out;
}
public static void main(String[] args) {
System.out.println(spiral(new int[][]{{1, 2, 3}, {4, 5, 6}, {7, 8, 9}}));
}
}
[1, 2, 3, 6, 9, 8, 7, 4, 5]
Common mistakes
- Mixing up
RandCon a non-square matrix (len(m)is rows,len(m[0])is columns). - Creating a grid with
[[0] * C] * Rin Python — every row is the same list, so changing one row changes all of them. Use[[0] * C for _ in range(R)]. - Reading
grid[nr][nc]before checking0 ≤ nr < R and 0 ≤ nc < C. - In spiral order, forgetting the two
ifchecks, which repeats the middle row or column.
Quick recap
- Every full traversal is O(R × C); the question is only the order.
- Spiral: four shrinking borders, with checks for the last row/column.
- Rotate 90° clockwise = transpose + reverse each row.
- Same diagonal: equal
r − c; same anti-diagonal: equalr + c. - Neighbours: direction arrays plus a bounds check; BFS on a grid gives shortest paths.