Introduction

A zig-zag scan visits an N x N matrix along diagonals, alternating direction each time. This traversal appears in signal-processing and compression workflows because it groups nearby low-frequency positions early, but it is also a useful general matrix traversal problem.

The Core Observation

Every diagonal in a matrix has the same value of row + col. That means you can iterate over diagonal sums from 0 to 2N - 2 and collect the cells belonging to each diagonal.

The zig-zag behavior comes from alternating how you output those diagonals:

• one diagonal is emitted upward
• the next is emitted downward

This is much easier to reason about than hand-writing a long sequence of movement rules.

Python Implementation

1from typing import List
2
3
4def zigzag_scan(matrix: List[List[int]]) -> List[int]:
5    n = len(matrix)
6    if n == 0 or any(len(row) != n for row in matrix):
7        raise ValueError("matrix must be non-empty and square")
8
9    result: List[int] = []
10
11    for s in range(2 * n - 1):
12        diagonal = []
13        row_start = max(0, s - (n - 1))
14        row_end = min(n - 1, s)
15
16        for row in range(row_start, row_end + 1):
17            col = s - row
18            diagonal.append(matrix[row][col])
19
20        if s % 2 == 0:
21            diagonal.reverse()
22
23        result.extend(diagonal)
24
25    return result
26
27
28matrix = [
29    [1, 2, 3],
30    [4, 5, 6],
31    [7, 8, 9],
32]
33
34print(zigzag_scan(matrix))

Output:

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

This approach is clean because each element is visited exactly once.

Why the Direction Alternates

If you list matrix positions by diagonal sum, the diagonals are:

• sum 0: (0, 0)
• sum 1: (0, 1), (1, 0)
• sum 2: (0, 2), (1, 1), (2, 0)

To get the standard zig-zag pattern, reverse every other diagonal before appending it.

That is what the if s % 2 == 0: diagonal.reverse() line is doing.

Inverse Operation: Rebuild the Matrix

If you have the zig-zag sequence and want to reconstruct the matrix, use the same diagonal traversal order in reverse.

1def zigzag_unscan(values: List[int], n: int) -> List[List[int]]:
2    if len(values) != n * n:
3        raise ValueError("value count must equal n*n")
4
5    matrix = [[0] * n for _ in range(n)]
6    index = 0
7
8    for s in range(2 * n - 1):
9        coords = []
10        row_start = max(0, s - (n - 1))
11        row_end = min(n - 1, s)
12
13        for row in range(row_start, row_end + 1):
14            coords.append((row, s - row))
15
16        if s % 2 == 0:
17            coords.reverse()
18
19        for row, col in coords:
20            matrix[row][col] = values[index]
21            index += 1
22
23    return matrix

A good test is that zigzag_unscan(zigzag_scan(matrix), n) should reproduce the original matrix.

Complexity

The scan runs in O(N^2) time because the matrix has N^2 elements and each one is touched once.

The extra memory is O(N) for the temporary diagonal list in the straightforward implementation.

That is efficient enough for most practical matrix sizes.

Where Zig-Zag Order Is Used

The classic example is JPEG-style coefficient ordering after block transforms. In that context, zig-zag order tends to place many low-frequency values first and long runs of zeros later, which helps downstream run-length encoding.

Even outside compression, it is a neat exercise in structured traversal because it rewards finding the underlying diagonal pattern instead of manually steering across the grid.

Common Pitfalls

A common mistake is trying to move cell by cell with many edge-condition branches. That usually produces off-by-one bugs.

Another pitfall is forgetting to validate that the matrix is square. A zig-zag scan of a general rectangular matrix is possible, but it is a different problem from the one stated here.

Developers also sometimes reverse the wrong diagonal parity and get a mirrored traversal order.

Finally, always test tiny sizes such as 1 x 1, 2 x 2, and 3 x 3. Small cases expose traversal mistakes quickly.

Summary

• A zig-zag scan traverses matrix diagonals in alternating directions.
• Diagonal grouping works because cells on the same diagonal share row + col.
• A diagonal-sum loop gives a clean O(N^2) solution.
• Reversing every other diagonal produces the standard zig-zag order.
• Small boundary tests are the fastest way to validate correctness.