126. Diagonal Zigzag Traversal

Why this mechanism works

A diagonal is identified by its coordinate sum. Compute the legal row range for each sum and derive the column as sum-row. Collecting in increasing row order gives one direction; reverse every even-numbered diagonal to obtain the required zigzag.

State and boundaries

diagonal identifies r+c. The legal row interval clips that diagonal to the matrix bounds.

Protocol

1. Iterate coordinate sums from zero to rows+cols-2.
2. Collect cells with legal rows and column diagonal-row.
3. Reverse the collected values on even sums.
4. Append them to output.

Visualization

matrix 1 2 3 / 4 5 6 / 7 8 9
diagonals: [1], [2,4], [7,5,3], [6,8], [9]

Python implementation

def diagonal_zigzag(matrix):
    if not matrix or not matrix[0]:
        return []
    rows, cols = len(matrix), len(matrix[0])
    output = []
    for diagonal in range(rows + cols - 1):
        first = max(0, diagonal - cols + 1)
        last = min(rows - 1, diagonal)
        values = [matrix[r][diagonal - r] for r in range(first, last + 1)]
        if diagonal % 2 == 0:
            values.reverse()
        output.extend(values)
    return output

Worked execution

Recorded state changes after statements; L numbers refer to the solution file. Long traces are explicitly condensed.

L2 diagonal_zigzag: if not matrix or not matrix[0]:
matrix=[[1, 2, 3], [4, 5, 6], [7, 8, 9]]

L4 diagonal_zigzag: rows, cols = len(matrix), len(matrix[0])
matrix=[[1, 2, 3], [4, 5, 6], [7, 8, 9]]; rows=3; cols=3

L5 diagonal_zigzag: output = []
matrix=[[1, 2, 3], [4, 5, 6], [7, 8, 9]]; rows=3; cols=3; output=[]

L6 diagonal_zigzag: for diagonal in range(rows + cols - 1):
matrix=[[1, 2, 3], [4, 5, 6], [7, 8, 9]]; rows=3; cols=3; output=[]; diagonal=0

L7 diagonal_zigzag: first = max(0, diagonal - cols + 1)
matrix=[[1, 2, 3], [4, 5, 6], [7, 8, 9]]; rows=3; cols=3; output=[]; diagonal=0; first=0

L8 diagonal_zigzag: last = min(rows - 1, diagonal)
matrix=[[1, 2, 3], [4, 5, 6], [7, 8, 9]]; rows=3; cols=3; output=[]; diagonal=0; first=0; last=0

L9 diagonal_zigzag: values = [matrix[r][diagonal - r] for r in range(first, last + 1)]
matrix=[[1, 2, 3], [4, 5, 6], [7, 8, 9]]; rows=3; cols=3; output=[]; diagonal=0; first=0; last=0; r=0

L9 diagonal_zigzag: values = [matrix[r][diagonal - r] for r in range(first, last + 1)]
matrix=[[1, 2, 3], [4, 5, 6], [7, 8, 9]]; rows=3; cols=3; output=[]; diagonal=0; first=0; last=0; values=[1]

... 22 intermediate state changes omitted ...

L7 diagonal_zigzag: first = max(0, diagonal - cols + 1)
matrix=[[1, 2, 3], [4, 5, 6], [7, 8, 9]]; rows=3; cols=3; output=[1, 2, 4, 7, 5, 3, 6, 8]; diagonal=4; first=2; last=2; values=[6, 8]

L9 diagonal_zigzag: values = [matrix[r][diagonal - r] for r in range(first, last + 1)]
matrix=[[1, 2, 3], [4, 5, 6], [7, 8, 9]]; rows=3; cols=3; output=[1, 2, 4, 7, 5, 3, 6, 8]; diagonal=4; first=2; last=2; values=[6, 8]; r=2

L9 diagonal_zigzag: values = [matrix[r][diagonal - r] for r in range(first, last + 1)]
matrix=[[1, 2, 3], [4, 5, 6], [7, 8, 9]]; rows=3; cols=3; output=[1, 2, 4, 7, 5, 3, 6, 8]; diagonal=4; first=2; last=2; values=[9]

L12 diagonal_zigzag: output.extend(values)
matrix=[[1, 2, 3], [4, 5, 6], [7, 8, 9]]; rows=3; cols=3; output=[1, 2, 4, 7, 5, 3, 6, 8, ...]; diagonal=4; first=2; last=2; values=[9]

L2 diagonal_zigzag: if not matrix or not matrix[0]:
matrix=[[1, 2, 3]]

L4 diagonal_zigzag: rows, cols = len(matrix), len(matrix[0])
matrix=[[1, 2, 3]]; rows=1; cols=3

L5 diagonal_zigzag: output = []
matrix=[[1, 2, 3]]; rows=1; cols=3; output=[]

L6 diagonal_zigzag: for diagonal in range(rows + cols - 1):
matrix=[[1, 2, 3]]; rows=1; cols=3; output=[]; diagonal=0

L7 diagonal_zigzag: first = max(0, diagonal - cols + 1)
matrix=[[1, 2, 3]]; rows=1; cols=3; output=[]; diagonal=0; first=0

L8 diagonal_zigzag: last = min(rows - 1, diagonal)
matrix=[[1, 2, 3]]; rows=1; cols=3; output=[]; diagonal=0; first=0; last=0

L9 diagonal_zigzag: values = [matrix[r][diagonal - r] for r in range(first, last + 1)]
matrix=[[1, 2, 3]]; rows=1; cols=3; output=[]; diagonal=0; first=0; last=0; r=0

L9 diagonal_zigzag: values = [matrix[r][diagonal - r] for r in range(first, last + 1)]
matrix=[[1, 2, 3]]; rows=1; cols=3; output=[]; diagonal=0; first=0; last=0; values=[1]

... 5 intermediate state changes omitted ...

L6 diagonal_zigzag: for diagonal in range(rows + cols - 1):
matrix=[[1, 2, 3]]; rows=1; cols=3; output=[1, 2]; diagonal=2; first=0; last=0; values=[2]

L9 diagonal_zigzag: values = [matrix[r][diagonal - r] for r in range(first, last + 1)]
matrix=[[1, 2, 3]]; rows=1; cols=3; output=[1, 2]; diagonal=2; first=0; last=0; values=[2]; r=0

L9 diagonal_zigzag: values = [matrix[r][diagonal - r] for r in range(first, last + 1)]
matrix=[[1, 2, 3]]; rows=1; cols=3; output=[1, 2]; diagonal=2; first=0; last=0; values=[3]

L12 diagonal_zigzag: output.extend(values)
matrix=[[1, 2, 3]]; rows=1; cols=3; output=[1, 2, 3]; diagonal=2; first=0; last=0; values=[3]

Why the solution is correct

Every cell has one unique coordinate sum and appears once in that diagonal's legal row range. Alternating reversal supplies the required direction without changing membership. Concatenating diagonals in increasing sum gives the complete traversal.

Time and space

O(rows*cols) time; O(min(rows,cols)) temporary diagonal space plus O(rows*cols) output.

Common mistakes

Assuming every diagonal has the same length fails near boundaries. Reversing odd rather than even sums produces the opposite initial direction.

Reasoning card

Transfer exercise

Emit each diagonal directly in its desired row direction instead of allocating a temporary list.