Zigzag Traversal of a Matrix Along Its Anti-Diagonals

Given an `m x n` matrix of integers, return all of its elements in zigzag order along the anti-diagonals. Cell `(i, j)` (row `i`, column `j`, both 0-indexed) lies on anti-diagonal `d = i + j`. Visit the anti-diagonals in increasing order of `d`, from `d = 0` (the top-left cell) to `d = m + n - 2` (the bottom-right cell), and alternate the direction of travel: - When `d` is even, walk the anti-diagonal upward: start at its cell with the largest row index and end at its cell with the smallest row index (bottom-left to top-right). - When `d` is odd, walk it downward: start at its cell with the smallest row index and end at the largest (top-right to bottom-left). Only cells inside the matrix are visited. Return the values in the order the cells are visited. ### Function Signature ```python def zigzag_diagonal_order(mat: list[list[int]]) -> list[int]: ``` ### Rules - The matrix is rectangular: every row has the same length `n`. - Every cell appears exactly once in the output, so the result has length `m * n`. - The order is fully determined by the anti-diagonal and direction rules above. ### Constraints - `1 <= m <= 10^4` and `1 <= n <= 10^4` - `1 <= m * n <= 10^4` - `-10^5 <= mat[i][j] <= 10^5` ### Examples **Example 1** ```text Input: mat = [[1, 2, 3], [4, 5, 6], [7, 8, 9]] Output: [1, 2, 4, 7, 5, 3, 6, 8, 9] ``` Anti-diagonal 1 (odd) goes down from 2 to 4; anti-diagonal 2 (even) goes up from 7 through 5 to 3. **Example 2** ```text Input: mat = [[1, 2, 3, 4], [5, 6, 7, 8]] Output: [1, 2, 5, 6, 3, 4, 7, 8] ``` **Example 3** ```text Input: mat = [[1], [2], [3]] Output: [1, 2, 3] ```