DSA Visualizer
GRID

Diagonal Traversal

Every cell where i + j is the same sits on one anti-diagonal. Visit the diagonals one by one, corner to corner.

Cells grouped by i + j: corner first, then each anti-diagonal down to the opposite corner.

0
1
2
3
0
1
2
3
4
1
5
6
7
8
2
9
10
11
12
Visited
Press play to start
Diagonal order groups cells by i + j: first the corner, then the two cells next to it, and so on down to the opposite corner.
0
VisitedVisited
12
LeftRemaining
12
TotalTotal
1 / 20

Pseudocode

Diagonal
1for d in 0 .. rows+cols-2:
2 for i in max(0, d-cols+1) .. min(d, rows-1):
3 j = d - i
4 visit(a[i][j])

Legend

Visiting nowNew directionVisited

Grid size

Want your own values? Edit this grid in the 2D Array Visualizer →

Tip: Space play/pause · ← → step

Learn diagonal traversal

Diagonal traversal groups cells by the sum of their indices. All the cells where i + j = 0 come first (just the corner), then the cells where i + j = 1, and so on until the opposite corner. Each group is one anti-diagonal.

A traversal is just a rule for the order in which you visit cells. The grid does not change; only the path through it does. Compare it with row-major, column-major, snake, boundary and spiral.

Every full traversal costs one step per cell, rows × cols, which is written O(rows · cols). Boundary is the exception: it visits only the outer ring.

How diagonal traversal works

Draw a grid and shade every cell whose row number plus column number is 2: cells [0][2], [1][1] and [2][0]. They form a slanted line from the top right down to the bottom left, an anti-diagonal. Every cell in the grid belongs to exactly one such line, and the lines are numbered by that sum, d = i + j.

Diagonal traversal visits the lines in order: d = 0 is just the top-left corner, d = 1 has two cells, and the lines grow until they hit the far edges and shrink again down to the bottom-right corner. It is the order you would sweep a grid with a ruler held at forty-five degrees.

The precondition is the same as always: a rectangle. In the visualizer the variable d shows the current diagonal and the first cell of each line is marked as a turn.

The loop shape

The outer loop runs d from 0 to rows + cols − 2. For each diagonal the inner loop runs i through the rows that line touches, and the column follows for free: j = d − i.

The only tricky part is where i starts and stops. Near the top-left corner it starts at 0, but once the diagonal reaches the right edge it has to start lower, at d − cols + 1, or j would fall off the grid. Near the bottom it has to stop at rows − 1 rather than at d. Hence max(0, d − cols + 1) and min(d, rows − 1). Step through the visualizer and watch those bounds change at diagonals 3 and 4.

A worked example: a 3 × 4 grid

With the cells numbered 1 to 12, the six diagonals read:

1 → 2 → 5 → 3 → 6 → 9 → 4 → 7 → 10 → 8 → 11 → 12

Grouped by diagonal that is 1 | 2 5 | 3 6 9 | 4 7 10 | 8 11 | 12: the lines grow to three cells, then shrink. Twelve cells, twelve steps, six diagonals, exactly 3 + 4 − 1.

Where you'll meet it

  • JPEG compression. After the transform step, each 8 × 8 block is read in a zigzag along its anti-diagonals so the small high-frequency values cluster at the end.
  • Dynamic programming tables. In problems such as longest common subsequence, every cell on one anti-diagonal depends only on earlier diagonals, so a whole diagonal can be computed at once, in parallel.
  • Pairing and enumeration. Listing all pairs (i, j) by their sum is how you enumerate an infinite grid one finite diagonal at a time.
  • Interviews. “Diagonal traverse” and “print the matrix diagonally” are standard warm-ups.

Mistakes beginners make

  • Running i from 0 to d every time. That works on the first few diagonals and then indexes outside the grid.
  • Confusing the two kinds of diagonal. Cells with i − j constant form the main diagonals, which slope the other way. This page uses i + j.
  • Assuming the grid is square. The bounds above are what make a 3 × 4 grid work; on a square grid a simpler, wrong version can pass by luck.

Every order so far visited every cell. Next, one that only walks the outer ring: Boundary traversal →

Diagonal traversal questions

What is diagonal traversal of a matrix?

Visiting the cells one anti-diagonal at a time. An anti-diagonal is the set of cells whose row and column indices add up to the same number: i + j = 0 is the top-left corner, i + j = 1 is the two cells next to it, and the last diagonal is the bottom-right corner alone.

How many diagonals does a matrix have?

rows + cols − 1. A 3 × 4 grid has 6 anti-diagonals, numbered 0 to 5, because the largest possible i + j is (3 − 1) + (4 − 1) = 5.

Why does the inner loop start at max(0, d − cols + 1)?

Because j = d − i must stay inside the grid. When d is larger than cols − 1, starting i at 0 would give a column past the right edge, so i has to start at d − cols + 1. The min(d, rows − 1) upper bound stops i running past the bottom row in the same way.

Is this the same as LeetCode's diagonal traverse?

Almost. LeetCode 498 walks the same anti-diagonals but alternates direction on each one, up-right then down-left, like a snake. The version here always goes down-left, which is simpler to write and the usual first step before adding the alternation.