Matrix Diagonal Traversal

Before we start

By the end of this page you will be able to:

• See why all cells on the same anti-diagonal share a single number (row + col).
• Explain out loud how to collect diagonals in order using that key.
• Recognise this pattern in diagonal sort, anti-diagonal grouping, and the classic Diagonal Traverse problem.

Stop at every Pause & Think box. The key insight here is a small but surprising mathematical observation — give it a moment to land.

Picture this first (no code yet)

That gutter number — row + col — is the diagonal key. Every anti-diagonal in a matrix is uniquely identified by it. The whole pattern is: group cells by their key, then read each group.

The actual problem

Given an m × n matrix, return all elements collected anti-diagonal by anti-diagonal, alternating direction (up-right, then down-left, then up-right…).

input:
  [[1, 2, 3],
   [4, 5, 6],
   [7, 8, 9]]

output: [1, 2, 4, 7, 5, 3, 6, 8, 9]

Anti-diagonal 0: {(0,0)} → [1] (up → direction: single cell) Anti-diagonal 1: {(0,1),(1,0)} → [2,4] (going down-left) Anti-diagonal 2: {(0,2),(1,1),(2,0)} → [7,5,3] (going up-right — reversed) Anti-diagonal 3: {(1,2),(2,1)} → [6,8] (going down-left) Anti-diagonal 4: {(2,2)} → [9] (single cell)

Notice: even-numbered diagonals go one way, odd-numbered go the other.

First, the slow way (so you feel the pain)

Most beginners try to manually craft the traversal direction — moving up-right until hitting a wall, then stepping down or left, then moving down-left until hitting a wall, then stepping right or down, alternating forever. The wall-handling code has four separate cases, each slightly different, and getting all four right without off-by-one errors is genuinely hard.

# Direction-simulation — 4 wall cases, fragile
r, c = 0, 0
going_up = True
result = []
for _ in range(m * n):
    result.append(matrix[r][c])
    if going_up:
        if c == n - 1:          # hit right wall — step down
            r += 1; going_up = False
        elif r == 0:            # hit top wall — step right
            c += 1; going_up = False
        else:
            r -= 1; c += 1
    else:
        if r == m - 1:          # hit bottom wall — step right
            c += 1; going_up = True
        elif c == 0:            # hit left wall — step down
            r += 1; going_up = True
        else:
            r += 1; c -= 1

This is O(m×n) in time but O(1) space — the cost is purely cognitive: four wall cases is a lot to hold in your head and get exactly right under interview pressure.

The grouping approach reduces those four cases to zero. The direction simply comes from whether the diagonal index is even or odd.

The turning point

The anti-diagonal key d = row + col is the insight. Let's stare at a small matrix to see it:

     col=0  col=1  col=2
row=0  [1]    [2]    [3]
row=1  [4]    [5]    [6]
row=2  [7]    [8]    [9]

d = row + col:
     col=0  col=1  col=2
row=0   0      1      2
row=1   1      2      3
row=2   2      3      4

Every cell where row + col = 2 is: (0,2), (1,1), (2,0). They form exactly one anti-diagonal.

For an m × n matrix, row + col ranges from 0 (top-left corner) to (m-1) + (n-1) = m+n-2 (bottom-right corner). So there are exactly m + n - 1 anti-diagonals.

The one idea to remember

Watch it happen, frame by frame

Step 1: Group all cells by d = row + col.

d=0: [(0,0)]
d=1: [(0,1), (1,0)]
d=2: [(0,2), (1,1), (2,0)]
d=3: [(1,2), (2,1)]
d=4: [(2,2)]

Step 2: For each group, decide the direction.

Even d (0, 2, 4): traverse upward (larger row → smaller row, i.e. bottom-left to top-right). Odd d (1, 3): traverse downward (smaller row → larger row, i.e. top-right to bottom-left).

d=0 (even, up):   [(0,0)]           → values [1]
d=1 (odd, down):  [(0,1),(1,0)]     → values [2,4]
d=2 (even, up):   [(2,0),(1,1),(0,2)] → values [7,5,3]
d=3 (odd, down):  [(1,2),(2,1)]     → values [6,8]
d=4 (even, up):   [(2,2)]           → values [9]

Result: [1, 2, 4, 7, 5, 3, 6, 8, 9]  ✅

[[1, 2],
 [3, 4],
 [5, 6]]

m=3, n=2 → diagonals d = 0 to 3.

d=0 (even, up):  [(0,0)] → [1]
d=1 (odd, down): [(0,1),(1,0)] → [2,3]
d=2 (even, up):  [(2,0),(1,1)] → [5,4]
d=3 (odd, down): [(2,1)] → [6]

Result: [1, 2, 3, 5, 4, 6]

Now, the code — line by line

Approach 1: Grouping (easiest to understand)

def findDiagonalOrder_grouped(matrix):
    if not matrix or not matrix[0]:
        return []

    m, n = len(matrix), len(matrix[0])
    diagonals = [[] for _ in range(m + n - 1)]   # one list per anti-diagonal

    for row in range(m):
        for col in range(n):
            diagonals[row + col].append(matrix[row][col])   # group by key

    result = []
    for d, group in enumerate(diagonals):
        if d % 2 == 0:
            result.extend(reversed(group))   # even: bottom-left to top-right
        else:
            result.extend(group)             # odd: top-left to bottom-right
    return result

• diagonals[row + col].append(...) — every cell files itself into its gutter bucket.
• if d % 2 == 0: reversed(group) — even-indexed diagonals go upward, so reverse the bucket (which was filled top-to-bottom).
• O(m×n) time, O(m×n) extra space for the buckets.

Approach 2: Direct walk (O(1) extra space)

For each diagonal index d, compute the starting cell and step direction directly:

def findDiagonalOrder(matrix):
    if not matrix or not matrix[0]:
        return []

    m, n = len(matrix), len(matrix[0])
    result = []

    for d in range(m + n - 1):
        if d % 2 == 0:                         # going up-right
            r = min(d, m - 1)                  # start as low as possible
            c = d - r                          # c = d - r
            while r >= 0 and c < n:
                result.append(matrix[r][c])
                r -= 1; c += 1
        else:                                  # going down-left
            c = min(d, n - 1)                  # start as far right as possible
            r = d - c                          # r = d - c
            while c >= 0 and r < m:
                result.append(matrix[r][c])
                r += 1; c -= 1

    return result

Key observations:

• r = min(d, m-1) — on a diagonal d, the starting row is d (if d is still inside the matrix) or m-1 (if we've run out of rows). Same logic for columns.
• c = d - r — once we know r, column is d - r because r + c = d.
• The step (r--, c++) or (r++, c--) follows the diagonal direction naturally.

Why is it always correct?

For every cell (r, c) in the matrix, r + c is a unique identifier for its anti-diagonal. By iterating d from 0 to m+n-2, we visit every anti-diagonal exactly once. Within each diagonal, we visit every cell exactly once (walking from one end to the other). Together, every cell is visited exactly once.

Time: O(m × n) — one constant-work step per cell. Space: O(m×n) for the grouping approach; O(1) for the direct-walk approach (output excluded).

When should I reach for this? (the trigger list)

Reach for the diagonal-key trick when:

• Asked to traverse or collect a matrix diagonally (anti-diagonal or main diagonal).
• Asked to sort diagonals of a matrix independently.
• Asked to group matrix elements where the grouping criterion is "same anti-diagonal" or "same diagonal."
• You see a 2D problem where row + col (or row - col) stays constant along the path of interest.
• The problem involves LCS/DP where diagonals in a 2D DP table represent equal-length subproblems.

Whenever you spot a constraint of the form row + col = constant or row - col = constant, the diagonal key is at work.

The same trick in three disguises

Disguise 1 — Sort the Matrix Diagonally (LC #1329)

For each main diagonal (where row - col = constant), sort the elements independently and put them back.

def diagonalSort(mat):
    from collections import defaultdict
    import heapq
    m, n = len(mat), len(mat[0])
    diags = defaultdict(list)

    for r in range(m):
        for c in range(n):
            diags[r - c].append(mat[r][c])   # key = row - col for main diagonals

    for key in diags:
        diags[key].sort(reverse=True)        # sort descending (we'll pop from end)

    for r in range(m):
        for c in range(n):
            mat[r][c] = diags[r - c].pop()   # place sorted values back

    return mat

The key here is row - col (constant along main diagonals) instead of row + col (constant along anti-diagonals). Same concept, different direction.

Disguise 2 — Anti-diagonal groups in DP

In dynamic-programming problems on a 2D table (like Longest Common Subsequence), cells on the same anti-diagonal (i + j = constant) are independent and can be computed in parallel (useful for parallelism) or filled in diagonal order to ensure dependencies are met.

Disguise 3 — N-Queens diagonal conflict check

Two queens at (r1, c1) and (r2, c2) are on the same anti-diagonal if r1 + c1 == r2 + c2, and on the same main diagonal if r1 - c1 == r2 - c2. Using sets of these two values instantly tells you if a new queen conflicts diagonally — O(1) per check.

anti_diagonals = set()   # stores r + c for each placed queen
main_diagonals = set()   # stores r - c for each placed queen

def can_place(r, c):
    return (r + c) not in anti_diagonals and (r - c) not in main_diagonals

Traps that catch beginners

Say it like a pro (interview one-liner)

"The key insight is that every cell on the same anti-diagonal shares the same row + col value. I group all cells by this key — giving exactly m + n - 1 groups — then traverse each group in alternating direction (even key upward, odd key downward). This visits every cell exactly once in O(m×n) time."

Check yourself

Practice problems

When you can explain the row + col key in one sentence and code the grouped approach from memory, you've learned this pattern.

Next up: Matrix Search — Sorted Matrix — where we exploit a sorted 2D grid using the staircase search trick you first met in Two Pointers.