← DSA Atlas
Dedicated problem page · #498

Diagonal Traverse

MediumMatrix and SimulationAnti-diagonal grouping with alternating sweepMatrix traversal by constant i+j diagonals
Solve on LeetCode ↗
498
MediumMatrix and SimulationMatrix traversal by constant i+j diagonalsAnti-diagonal grouping with alternating sweep

Diagonal Traverse

Given an m x n matrix mat, return all its elements in diagonal order. Traversal starts at the top-left cell and walks the anti-diagonals (cells where row + col is constant), reversing direction on each successive diagonal: the first diagonal goes up-right, the next goes down-left, and so on.

Open official problem prompt ↗
In plain English

Flatten a 2D grid into a 1D list where elements come out along anti-diagonals, with the walk direction flipping on each diagonal so the reading path is continuous.

Picture it like this

Think of a boustrophedon plow: the farmer plows one furrow up the field, then turns and plows the next furrow back down, alternating direction each pass so no time is wasted returning to the start.

Example
Input
mat = [[1,2,3],[4,5,6],[7,8,9]]
Output
[1,2,4,7,5,3,6,8,9]
Why
Diagonal 0 = [1] (up), diagonal 1 = [2,4] (down), diagonal 2 = [7,5,3] (up), diagonal 3 = [6,8] (down), diagonal 4 = [9], concatenated in that order.
Constraints
m == mat.lengthn == mat[i].length1 <= m, n <= 10^41 <= m * n <= 10^4-10^5 <= mat[i][j] <= 10^5
Pattern lesson

See the pattern, then code

Anti-diagonal grouping with alternating sweep
Recognition clue

Every cell on one anti-diagonal shares the same row+col sum, and the output zig-zags between diagonals. A request to read a grid 'diagonally' with flipping direction is the tell.

↗
Matrix and Simulation

Rotations, boundary walks, direction changes, or careful in-place state updates.. Group cells by d = row + col. There are m+n-1 such diagonals. Emit each diagonal fully, but reverse the emission order on odd-indexed diagonals so the path stays connected without backtracking.

New words, made simpleKnow these before the algorithm
Anti-diagonal
The set of cells whose row index plus column index equals the same constant d.
Boustrophedon order
A back-and-forth traversal that reverses direction on each successive line or diagonal.
Approaches from first idea to best ideaCompare the trade-offs
ApproachHow it thinksCost
Collect then reverse alternate diagonals

Correct but wastes memory storing every diagonal in intermediate lists.

Bucket cells into a dictionary keyed by row+col, then output each bucket, reversing every other one.

Time O(m*n)Space O(m*n)
Best choiceDirect alternating sweep

Visits each cell once with only O(1) extra space beyond the output.

Iterate d over all diagonals and walk each one up or down directly into the result, clamping the start cell to the matrix bounds.

Time O(m*n)Space O(1)
The rule we keep true

Invariant

When processing diagonal d, every cell appended satisfies row + col == d and lies inside the matrix, and all diagonals 0..d-1 have already been fully emitted in the correct direction.

Why this is correct

Reasoning

Every matrix cell has a unique row+col value between 0 and m+n-2, so iterating d over that full range and emitting all in-bounds cells with that sum touches each cell exactly once. Flipping the sweep direction on odd d produces the required zig-zag path.

The algorithm in three movesSay these aloud before coding
1Loop d from 0 to m+n-2 over each anti-diagonal

d=1 (down): append mat[0][1]=2, mat[1][0]=4

2If d is even, walk the diagonal upward: start at the lowest valid row and go up-right

d=2 (up): append mat[2][0]=7, mat[1][1]=5, mat[0][2]=3

3If d is odd, walk it downward: start at the rightmost valid column and go down-left

result so far = [1,2,4,7,5,3]

4Clamp the start cell to stay inside the matrix, then append cells while in bounds

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example
10
21
32
43
54
65
76
87
98
1 · Readstart (0,0)
2 · AskWhich cells have row+col=0?
3 · Update stateresult=[]
4 · Resultappend 1 -> result=[1]
Key takeaway

The matrix in row-major order; highlighted cells 1, 2, 4 are the first diagonal (1) and second diagonal (2,4) emitted.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

  1. 1
    Lines 6Loop over every diagonal

    There are exactly m+n-1 anti-diagonals, indexed by d = row + col.

  2. 2
    Lines 7-13Even diagonal, sweep upward

    Start at the lowest valid row min(d, m-1); moving r up and c right keeps r+c=d until we leave the grid.

  3. 3
    Lines 14-20Odd diagonal, sweep downward

    Start at the rightmost valid column min(d, n-1); moving c left and r down keeps r+c=d, producing the reversed direction.

Make it stick

Edge cases, mistakes, and one self-check

E

Edge cases to test

  • Single row (m=1): output is just the row left to right
  • Single column (n=1): output is the column top to bottom
  • Single element 1x1 matrix returns that one element
  • Non-square matrices where m != n, so start-cell clamping matters
!

Common beginner mistakes

  • Forgetting to clamp the start cell with min(d, m-1) or min(d, n-1), causing index-out-of-range on later diagonals
  • Reversing the wrong parity of diagonals, yielding a valid-looking but incorrect order
  • Assuming the matrix is square and hardcoding n for m
Check your understanding

How many anti-diagonals does an m x n matrix have, and what is the maximum value of row+col?

More in Matrix and Simulation

#6Zigzag ConversionRow-index simulation with bouncing direction#48Rotate ImageTranspose then reverse rows#54Spiral MatrixShrinking boundary walk#59Spiral Matrix IIShrinking boundary fill#73Set Matrix ZeroesFirst row/column as marker storage#289Game of LifeIn-place bit-encoded next state