Diagonal Traverse: Matrix Zigzag Pattern

You are given an m x n matrix and need to return all elements in diagonal zigzag order. That means you walk along diagonals, alternating between going up-right and down-left. It sounds visual and intuitive when you draw it on paper, but translating that zigzag into clean code takes some thought.

This is LeetCode 498: Diagonal Traverse, a medium-difficulty problem. The matrix itself is not modified, and you are just reading elements in a specific order. The challenge is figuring out how to move through the matrix without going out of bounds and how to flip directions at the right time.

The problem

Given an m x n matrix mat, return an array of all the elements in diagonal order.

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

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

The traversal starts at mat[0][0], moves up-right along the first diagonal, then flips to down-left for the next diagonal, and keeps alternating until every element has been visited.

The brute force

One way to approach this is to collect elements diagonal by diagonal. Each diagonal consists of cells where row + col equals the same value. For a 3x3 matrix, the diagonals are:

• 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)

You iterate d from 0 to m + n - 2, collect all cells on each diagonal, and reverse every other diagonal to get the zigzag effect. This works fine, but it requires building intermediate lists for each diagonal before appending them to the result.

The key insight

Instead of collecting diagonals separately, you can simulate the traversal directly. Maintain a current position (r, c) and a direction flag. At each step, move in the current direction (up-right or down-left). When you hit a boundary, figure out where to go next and flip the direction.

The boundary handling is the core of the problem. When moving up-right (decreasing row, increasing column), you can hit:

• The top edge (r goes below 0): move right one column and flip direction.
• The right edge (c exceeds the last column): move down one row and flip direction.
• The top-right corner (both edges at once): move down one row and flip direction.

When moving down-left (increasing row, decreasing column), you can hit:

• The left edge (c goes below 0): move down one row and flip direction.
• The bottom edge (r exceeds the last row): move right one column and flip direction.
• The bottom-left corner (both edges at once): move right one column and flip direction.

Step-by-step walkthrough

Let's trace through the 3x3 matrix [[1,2,3],[4,5,6],[7,8,9]] and see which diagonal gets processed at each step. Green cells are already visited, and highlighted cells show the current diagonal being collected.

Notice how each diagonal is defined by cells sharing the same row + col sum. Even-sum diagonals go up-right, odd-sum diagonals go down-left. This alternation creates the zigzag pattern.

The code

def findDiagonalOrder(mat: list[list[int]]) -> list[int]:
    if not mat or not mat[0]:
        return []

    m, n = len(mat), len(mat[0])
    result = []
    r, c = 0, 0
    going_up = True

    for _ in range(m * n):
        result.append(mat[r][c])

        if going_up:
            if r == 0 and c == n - 1:
                r += 1
                going_up = False
            elif c == n - 1:
                r += 1
                going_up = False
            elif r == 0:
                c += 1
                going_up = False
            else:
                r -= 1
                c += 1
        else:
            if r == m - 1 and c == 0:
                c += 1
                going_up = True
            elif r == m - 1:
                c += 1
                going_up = True
            elif c == 0:
                r += 1
                going_up = True
            else:
                r += 1
                c -= 1

    return result

The loop runs exactly m * n times, once for each cell. At each iteration, we append the current cell to the result, then figure out where to move next based on the current direction and boundary conditions.

When going_up is true, we are moving diagonally up-right (row decreases, column increases). If we hit the top-right corner, the top edge, or the right edge, we adjust position and flip direction. The corner check (r == 0 and c == n - 1) must come first because it is a special case of both edge conditions.

The same logic applies in reverse when going_up is false. We move down-left, and hitting the bottom-left corner, bottom edge, or left edge triggers a direction change.

Complexity analysis

Time: we visit each cell exactly once in the main loop, performing O(1) work per cell. Total: O(m * n).

Space: the only extra variables are r, c, and going_up. The result array holds the output, which is required. Extra space is O(1).

Building blocks

The reusable pattern here is direction simulation in a 2D grid. You maintain a position and a direction state, advance the position each step, and handle boundary collisions by adjusting position and flipping direction.

r, c = 0, 0
going_up = True

for _ in range(m * n):
    process(mat[r][c])

    if going_up:
        # try to move up-right
        # handle top edge, right edge, corner
        # flip direction when hitting boundary
    else:
        # try to move down-left
        # handle bottom edge, left edge, corner
        # flip direction when hitting boundary

This skeleton shows up whenever you need to traverse a matrix in a non-standard order. The specific boundary checks change per problem, but the structure remains: move, check bounds, adjust, flip.

Other problems that use this pattern:

• Spiral Matrix (LeetCode 54): four directions instead of two, four boundaries instead of edges.
• Snake traversal: alternating left-to-right and right-to-left by row.
• Zigzag conversion (LeetCode 6): same up/down direction toggling but in a 1D context.

Edge cases

Before submitting, make sure your solution handles these:

• Empty matrix: [] or [[]] should return []. The guard at the top covers this.
• Single element: [[5]] returns [5]. The loop runs once and no boundary is hit.
• Single row: [[1, 2, 3]] returns [1, 2, 3]. Every step hits the top or bottom edge immediately, so you just move right.
• Single column: [[1], [2], [3]] returns [1, 2, 3]. Every step hits the left or right edge, so you just move down.
• Non-square matrix: a 2x4 or 5x2 matrix. The boundary checks handle rectangles correctly as long as you use m and n consistently.
• Large matrix: the simulation runs in O(m * n) with O(1) extra space, so it scales well.

From understanding to recall

You have seen how diagonal traversal works. The zigzag pattern, the boundary checks, the direction flipping. But during an interview, the tricky part is not understanding the idea. It is remembering the exact order of boundary checks and getting the corner cases right on the first try.

The boundary handling for this problem has six cases (three per direction), and the order matters. Mix them up and you get an infinite loop or skip a cell. This is exactly the kind of procedural detail that fades from memory after a few days.

Spaced repetition locks it in. You practice writing the direction simulation, the boundary checks, and the corner-first ordering from scratch. After a few spaced reps, the pattern is automatic. You see "diagonal order" in a problem and the boundary handling flows out without hesitation.

Related posts

• Spiral Matrix - another matrix traversal pattern
• Spiral Matrix II - generating spiral matrices
• Set Matrix Zeroes - in-place matrix manipulation

CodeBricks breaks Diagonal Traverse into its direction-simulation building block, then drills it independently with spaced repetition. You type the boundary checks, the corner-case ordering, and the direction flip from scratch until the whole pattern is automatic. When diagonal traversal shows up in your interview, you do not think about it. You just write it.