> ## Documentation Index
> Fetch the complete documentation index at: https://leetcode-py.wisl.dev/llms.txt
> Use this file to discover all available pages before exploring further.

> ## Agent Instructions
> leetcode-py is a Python LeetCode practice environment generator with one CLI: lcpy. It is not a service or platform.
> Each problem is a directory under leetcode/ with README.md, solution.py, test_solution.py, helpers.py, and playground.ipynb. lcpy gen creates them from JSON templates bundled with the package.
> Examples are backed by tests; copy them verbatim.

# Diagonal Traverse Python Solution with Tests

> Tested Python solution for LeetCode 498 with 12 pytest cases. Generate a practice environment with lcpy.

LeetCode 498, Medium. Topics: Array, Matrix, Simulation. [View on LeetCode](https://leetcode.com/problems/diagonal-traverse/description/).

Generate this problem as a practice environment: tested reference solution, 12 [parametrized pytest cases](/practice/testing), and a playground notebook:

```bash theme={"theme":{"light":"github-light","dark":"github-dark"}}
lcpy gen -n 498   # by problem number
lcpy gen -s diagonal_traverse   # by problem name
```

## Problem

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

### Examples

![Diagonal Traverse](https://assets.leetcode.com/uploads/2021/04/10/diag1-grid.jpg)

```
Input: mat = [[1,2,3],[4,5,6],[7,8,9]]
Output: [1,2,4,7,5,3,6,8,9]
```

```
Input: mat = [[1,2],[3,4]]
Output: [1,2,3,4]
```

### Constraints

* `m == mat.length`
* `n == mat[i].length`
* `1 <= m, n <= 10^4`
* `1 <= m * n <= 10^4`
* `-10^5 <= mat[i][j] <= 10^5`

## Solution

Reference implementation from [solution.py on GitHub](https://github.com/wislertt/leetcode-py/blob/main/leetcode/diagonal_traverse/solution.py), full suite in [test\_solution.py](https://github.com/wislertt/leetcode-py/blob/main/leetcode/diagonal_traverse/test_solution.py):

```python theme={"theme":{"light":"github-light","dark":"github-dark"}}
class Solution:
    """
    Diagonal Traverse Pattern:

    Matrix with coordinates:     d = i+j (diagonal index):
    1(0,0) 2(0,1) 3(0,2)       d=0: 1(0,0)           ↗
    4(1,0) 5(1,1) 6(1,2)       d=1: 2(0,1), 4(1,0)   ↙
    7(2,0) 8(2,1) 9(2,2)       d=2: 3(0,2), 5(1,1), 7(2,0)  ↗
                                d=3: 6(1,2), 8(2,1)   ↙
                                d=4: 9(2,2)           ↗

    'd' = diagonal number = sum of row+col indices (i+j)
    Each diagonal contains elements where i+j equals the same value

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

    # Time: O(m*n)
    # Space: O(1)
    def find_diagonal_order(self, mat: list[list[int]]) -> list[int]:
        m, n = len(mat), len(mat[0])
        result = []

        for d in range(m + n - 1):
            if d % 2 == 0:  # up-right diagonal
                for i in range(min(d, m - 1), max(-1, d - n), -1):
                    result.append(mat[i][d - i])
            else:  # down-left diagonal
                for i in range(max(0, d - n + 1), min(d + 1, m)):
                    result.append(mat[i][d - i])

        return result


class SolutionRowShift:
    """
    Row-shift approach: shift each row to align diagonals into columns

    Original matrix:    After shifting rows (col-row=actual_col):
    1 2 3              col=0  col=1  col=2  col=3  col=4
    4 5 6                1      2      3
    7 8 9                       4      5      6
                                       7      8      9
                         ↑      ↓      ↑      ↓      ↑

    Each row is shifted right by its row index, creating vertical columns
    from the original diagonals. Then alternate traversal direction.

    Traverse: 1 → 2,4 → 7,5,3 → 6,8 → 9
    """

    # Time: O(m*n)
    # Space: O(1)
    def find_diagonal_order(self, mat: list[list[int]]) -> list[int]:
        m, n = len(mat), len(mat[0])
        result = []

        for col in range(m + n - 1):
            if col % 2 == 1:  # upward
                for row in range(m):
                    i = col - row
                    if 0 <= i < n:
                        result.append(mat[row][i])
            else:  # downward
                for row in range(m - 1, -1, -1):
                    i = col - row
                    if 0 <= i < n:
                        result.append(mat[row][i])

        return result
```

## Complexity

| Time    | Space |
| ------- | ----- |
| O(m\*n) | O(1)  |

## Tags