loading

498. Diagonal Traverse — Step-by-Step Visualization

mediumLeetCode #498ArrayMatrixSimulation

Given an `m x n` matrix `mat`, return an array of all the elements of the array in a diagonal order. **Example 1:** Input: `mat = [[1,2,3],[4,5,6],[7,8,9]]` Output: `[1,2,4,7,5,3,6,8,9]` **Example 2:** Input: `mat = [[1,2],[3,4]]` Output: `[1,2,3,4]`

Algorithm Pattern

Diagonal Grouping

Key Idea

Every cell on the same diagonal shares the same index sum `i+j`. Group cells by this key, then reverse every even-numbered diagonal to produce the zig-zag order — no direction tracking needed.

Step-by-Step Approach

  1. Create a dictionary `d` where `d[i+j]` holds all cells on that diagonal.
  2. Iterate the matrix row by row; append `mat[i][j]` to `d[i+j]`.
  3. Iterate `d` in key order (0, 1, 2, …).
  4. If the diagonal level is even, reverse its list before appending to `ans`.
  5. If odd, append as-is.
  6. Return `ans`.

Common Gotchas

  • Python dicts preserve insertion order since 3.7 — iterating `d.items()` gives diagonals in order 0, 1, 2, …
  • Even diagonals go up-right (so elements were collected top-to-bottom and need reversing); odd diagonals go down-left and are already in the right order.

Related Problems

← All problems