Problem Statement

Diagonal Traverse

You are given a grid of numbers with m rows and n columns. We call this a matrix, which is just a fancy word for a rectangle of numbers laid out in rows and columns. Your job is to read out every number, but not row by row. Instead you read along the diagonals, and you zig-zag. The first diagonal goes up and to the right, the next goes down and to the left, then up-right again, and so on. Think of it like walking up a staircase, then back down the next one, then up again. The whole trick is this: keep track of which way you are heading, and when you bump into a wall (the edge of the grid), turn and start the next diagonal.

mediumMatrixMatrixTime: O(m*n) · Space: O(1)

Signals to notice

traverse matrix diagonallyalternating directionboundary handling

Brute force first

No simpler alternative — traversal IS the task. The challenge is getting the boundary logic right. That direct path helps you understand the question, but it tends to treat every possibility as brand new instead of learning from earlier steps.

The key insight

Iterate through 2*(m+n-1)-1 diagonals. Odd diagonals go up-right, even go down-left (or vice versa). For each diagonal, compute start position and traverse until out of bounds. The goal is not to be clever for its own sake, but to remember the one relationship that keeps the solution grounded as you move forward.

Trace it on `mat=[[1,2,3],[4,5,6],[7,8,9]] (m=3, n=3)`

start r=0,c=0,up=T | emit mat[0][0]=1 | r==0 so c=1, up=F
r=0,c=1,up=F | emit mat[0][1]=2 | interior so r=1,c=0
r=1,c=0,up=F | emit mat[1][0]=4 | c==0 so r=2, up=T
r=2,c=0,up=T | emit mat[2][0]=7 | interior so r=1,c=1
r=1,c=1,up=T | emit mat[1][1]=5 | interior so r=0,c=2
r=0,c=2,up=T | emit mat[0][2]=3 | c==n-1 so r=1, up=F
r=1,c=2,up=F | emit mat[1][2]=6 | interior so r=2,c=1
r=2,c=1,up=F | emit mat[2][1]=8 | r==m-1 so c=2, up=T; then emit mat[2][2]=9 (loop ends)
return [1,2,4,7,5,3,6,8,9]

What must stay true

There are m+n-1 diagonals. Elements on the same diagonal share the property that row+col is constant. The direction alternates with each diagonal. If that remains true after every update, the rest of the reasoning has a stable place to stand.

Shape of the loop

r, c, going_up = 0, 0, true
repeat m*n times:
  emit mat[r][c]
  if going_up:  c==n-1 ? (r++, flip) : r==0 ? (c++, flip) : (r--, c++)
  else:         r==m-1 ? (c++, flip) : c==0 ? (r++, flip) : (r++, c--)

Pseudocode only — the full worked solution lives in the Solution tab.

Easy way to go wrong

Getting the starting position wrong for each diagonal — when going up-right, start from the bottom-left of the diagonal. When going down-left, start from the top-right. The fix is usually to return to the meaning of each move, not just the steps themselves.

Matrix Pattern