Matrix traversal problems ask you to visit every cell of a 2D grid in a specific order. Spiral order uses four shrinking boundaries, diagonal order groups cells by row + col, and zigzag order is diagonal order with every other diagonal reversed. Each runs in O(rows x cols) time, and the bugs almost always come from non-square matrices, a single row or column, and off-by-one boundaries.
All examples are Python. They share this 3×4 test matrix, and the outputs shown were produced by running the code:
m = [[1, 2, 3, 4],
[5, 6, 7, 8],
[9, 10, 11, 12]]
Spiral order
Walk the outer ring clockwise, then repeat on the ring inside. Track four boundaries (top, bottom, left, right) and move each one inward after you finish the side it controls.
def spiral(matrix):
if not matrix or not matrix[0]:
return []
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): # left to right along the top
out.append(matrix[top][c])
top += 1
for r in range(top, bottom + 1): # down the right side
out.append(matrix[r][right])
right -= 1
if top <= bottom: # right to left along the bottom
for c in range(right, left - 1, -1):
out.append(matrix[bottom][c])
bottom -= 1
if left <= right: # up the left side
for r in range(bottom, top - 1, -1):
out.append(matrix[r][left])
left += 1
return out
print(spiral(m)) # [1, 2, 3, 4, 8, 12, 11, 10, 9, 5, 6, 7]
The two if checks are the part that matters. After the top row and right column are done, the remaining ring may have collapsed into a single row or column (for example the middle row of a 3-row matrix). Without the checks, you would walk that row a second time in the opposite direction and output duplicates. Test [[1,2,3]], [[1],[2],[3]] and a 3×4 matrix like the one above.
The direction-vector alternative
If boundary bookkeeping feels fragile, simulate a walker instead: keep going in the current direction, and turn right when the next cell is out of bounds or already visited.
def spiral_dirs(matrix):
if not matrix or not matrix[0]:
return []
R, C = len(matrix), len(matrix[0])
seen = [[False] * C for _ in range(R)]
dirs = [(0, 1), (1, 0), (0, -1), (-1, 0)] # right, down, left, up
r = c = d = 0
out = []
for _ in range(R * C):
out.append(matrix[r][c])
seen[r][c] = True
nr, nc = r + dirs[d][0], c + dirs[d][1]
if not (0 <= nr < R and 0 <= nc < C) or seen[nr][nc]:
d = (d + 1) % 4
nr, nc = r + dirs[d][0], c + dirs[d][1]
r, c = nr, nc
return out
This is harder to get wrong but uses O(rows x cols) extra memory for seen. I checked that both versions return the same order on 500 random matrices from 1×1 to 7×7. It is a good fallback when you are under time pressure.
Writing a spiral instead of reading one
“Spiral Matrix II” fills an n x n grid with 1..n² in spiral order. The boundary code is the same, but you assign instead of append:
def generate_spiral(n):
grid = [[0] * n for _ in range(n)]
top, bottom, left, right = 0, n - 1, 0, n - 1
k = 1
while top <= bottom and left <= right:
for c in range(left, right + 1):
grid[top][c] = k; k += 1
top += 1
for r in range(top, bottom + 1):
grid[r][right] = k; k += 1
right -= 1
if top <= bottom:
for c in range(right, left - 1, -1):
grid[bottom][c] = k; k += 1
bottom -= 1
if left <= right:
for r in range(bottom, top - 1, -1):
grid[r][left] = k; k += 1
left += 1
return grid
print(generate_spiral(3)) # [[1, 2, 3], [8, 9, 4], [7, 6, 5]]
Diagonal order
All cells on the same anti-diagonal (running from top-right to bottom-left) share the same value of row + col. That gives you a clean way to enumerate them with no special cases: loop over the sum s from 0 to rows + cols - 2, and for each s collect the cells that are inside the grid.
def diagonals(matrix):
if not matrix or not matrix[0]:
return []
R, C = len(matrix), len(matrix[0])
out = []
for s in range(R + C - 1):
r = max(0, s - (C - 1)) # first row where col = s - r is still inside
diag = []
while r < R and s - r >= 0:
diag.append(matrix[r][s - r])
r += 1
out.append(diag)
return out
print(diagonals(m))
# [[1], [2, 5], [3, 6, 9], [4, 7, 10], [8, 11], [12]]
For the other direction (top-left to bottom-right), cells share the same value of col - row, which ranges from -(R - 1) to C - 1:
def main_diagonals(matrix):
R, C = len(matrix), len(matrix[0])
return [[matrix[r][r + k] for r in range(R) if 0 <= r + k < C]
for k in range(-(R - 1), C)]
print(main_diagonals(m))
# [[9], [5, 10], [1, 6, 11], [2, 7, 12], [3, 8], [4]]
Knowing “same diagonal means same r + c or same c - r” also solves problems that never mention traversal, such as placing queens in N-Queens (track used diagonals in a set) or grouping cells in “Diagonal Traverse” and “Sort the Matrix Diagonally”.
Zigzag order
Zigzag (the “Diagonal Traverse” problem) visits the same anti-diagonals but alternates direction: the first goes up-right, the next down-left, and so on. Reusing diagonals, reverse every other one. The first diagonal has one cell, so the parity does not matter for it, but the second must be read from the bottom up: [5, 2].
def zigzag(matrix):
out = []
for s, diag in enumerate(diagonals(matrix)):
out.extend(diag if s % 2 else diag[::-1])
return out
print(zigzag(m)) # [1, 2, 5, 9, 6, 3, 4, 7, 10, 11, 8, 12]
Here diagonals lists each diagonal top-to-bottom, so odd-numbered ones are already in down-left order, and even-numbered ones are reversed to go up-right. This version uses O(rows + cols) extra memory per diagonal and is easy to reason about. If you are asked for O(1) extra space, simulate the walk instead:
def zigzag_walk(matrix):
if not matrix or not matrix[0]:
return []
R, C = len(matrix), len(matrix[0])
r = c = 0
up = True
out = []
for _ in range(R * C):
out.append(matrix[r][c])
if up:
if c == C - 1:
r += 1; up = False # hit the right edge: step down, turn around
elif r == 0:
c += 1; up = False # hit the top edge: step right, turn around
else:
r -= 1; c += 1
else:
if r == R - 1:
c += 1; up = True # hit the bottom edge: step right
elif c == 0:
r += 1; up = True # hit the left edge: step down
else:
r += 1; c -= 1
return out
The order of the edge checks matters. In the upward direction, check the right edge before the top edge, because in a corner such as the top-right cell you must go down, not right. The same applies in reverse for the bottom and left edges. Swapping these checks is the most common zigzag bug, and it only shows up on non-square matrices or specific corners. The two zigzag versions agree on 500 random matrices in my check.
Complexity
| Pattern | Time | Extra space (besides output) |
|---|---|---|
| Spiral (boundaries) | O(R x C) | O(1) |
| Spiral (visited grid) | O(R x C) | O(R x C) |
| Diagonals by r + c | O(R x C) | O(min(R, C)) per diagonal |
| Zigzag walk | O(R x C) | O(1) |
You cannot beat O(R x C) when every cell must be visited.
Common mistakes
- Assuming a square matrix. Always test a 1xN, an Nx1 and a 3×4. Most traversal bugs live there.
- Mixing up rows and columns.
len(matrix)is the number of rows,len(matrix[0])is the number of columns. Index asmatrix[row][col]. - Forgetting the empty matrix.
[]and[[]]are different, andmatrix[0]fails on the first. - Skipping the collapse checks in spiral. Duplicates in the middle row or column of an odd-sized matrix are the symptom.
- Counting by cells, not by structure. A loop that runs exactly
R * Ctimes, like the walker versions above, cannot terminate early or run forever, which makes it a safe frame for unfamiliar patterns.
Where these show up
Spiral order appears in interviews as “Spiral Matrix” and “Spiral Matrix II”, and the diagonal tricks cover “Diagonal Traverse”, “Sort the Matrix Diagonally” and “Toeplitz Matrix”. Once you can traverse in order, the next step is traversing with a purpose: finding paths through a grid. Our guides on matrix path problems and matrix operations continue from here. For hands-on practice with grids, try the 01 Matrix exercise and Unique Paths on AlgoCademy.
