Diagonal Matrix Traversal

Traversing a 2D matrix in specific patterns is a common and important algorithmic task with applications ranging from image processing and data serialization to game development. This challenge requires you to implement a particular "diagonal" traversal, extracting all elements from an m x n matrix into a single-dimensional list in a precise alternating up-right and down-left order.

Problem Description

You are given an m x n integer matrix, mat. Your goal is to return all elements of this matrix in a specific "diagonal order". The traversal begins from the top-left corner (mat[0][0]).

The diagonal order involves iterating through "diagonals", where a diagonal is defined by elements (r, c) such that their sum r + c is constant. The traversal processes these diagonals in increasing order of their sum k = r + c, from k=0 up to k = m + n - 2.

For each diagonal k:

1. If k is an even number (0, 2, 4, ...): Elements on this diagonal should be collected in an Up-Right fashion. This means starting from the element with the largest valid row index (and smallest valid column index) on that diagonal, and moving towards the element with the smallest valid row index (and largest valid column index). Effectively, you collect elements by decreasing row index and increasing column index.
   • Example: For k=2 in a 3x3 matrix, valid elements are mat[2][0], mat[1][1], mat[0][2]. Collecting Up-Right means mat[2][0] then mat[1][1] then mat[0][2].
2. If k is an odd number (1, 3, 5, ...): Elements on this diagonal should be collected in a Down-Left fashion. This means starting from the element with the smallest valid row index (and largest valid column index) on that diagonal, and moving towards the element with the largest valid row index (and smallest valid column index). Effectively, you collect elements by increasing row index and decreasing column index.
   • Example: For k=1 in a 3x3 matrix, valid elements are mat[0][1], mat[1][0]. Collecting Down-Left means mat[0][1] then mat[1][0].

You must collect all m * n elements into a single 1D list or array in this exact order.

Examples

Example 1:

Input: mat = [[1,2,3],[4,5,6],[7,8,9]]
Output: [1,2,4,3,5,7,6,8,9]
Explanation:
- Diagonal k=0 (even): Elements: mat[0][0]=1. Collect Up-Right: [1]. Result: [1]
- Diagonal k=1 (odd): Elements: mat[0][1]=2, mat[1][0]=4. Collect Down-Left: [2, 4]. Result: [1,2,4]
- Diagonal k=2 (even): Elements: mat[0][2]=3, mat[1][1]=5, mat[2][0]=7. Collect Up-Right: [7, 5, 3]. Result: [1,2,4,7,5,3]
- Diagonal k=3 (odd): Elements: mat[1][2]=6, mat[2][1]=8. Collect Down-Left: [6, 8]. Result: [1,2,4,7,5,3,6,8]
- Diagonal k=4 (even): Elements: mat[2][2]=9. Collect Up-Right: [9]. Result: [1,2,4,7,5,3,6,8,9]

Example 2:

Input: mat = [[1,2],[3,4],[5,6]]
Output: [1,2,3,5,4,6]
Explanation:
- Diagonal k=0 (even): Elements: mat[0][0]=1. Collect Up-Right: [1]. Result: [1]
- Diagonal k=1 (odd): Elements: mat[0][1]=2, mat[1][0]=3. Collect Down-Left: [2, 3]. Result: [1,2,3]
- Diagonal k=2 (even): Elements: mat[1][1]=4, mat[2][0]=5. Collect Up-Right: [5, 4]. Result: [1,2,3,5,4]
- Diagonal k=3 (odd): Elements: mat[2][1]=6. Collect Down-Left: [6]. Result: [1,2,3,5,4,6]

Example 3:

Input: mat = [[1],[2],[3]]
Output: [1,2,3]
Explanation:
- Diagonal k=0 (even): Elements: mat[0][0]=1. Collect Up-Right: [1]. Result: [1]
- Diagonal k=1 (odd): Elements: mat[1][0]=2. Collect Down-Left: [2]. Result: [1,2]
- Diagonal k=2 (even): Elements: mat[2][0]=3. Collect Up-Right: [3]. Result: [1,2,3]

Constraints

• m is the number of rows, n is the number of columns.
• 1 <= m, n <= 100
• 1 <= mat[i][j] <= 10^5
• The matrix mat will always be non-empty.
• Your solution should aim for a time complexity of O(mn) and space complexity of O(mn) to store the result.

Notes

• A common approach involves iterating through all possible diagonal sums k. For each k, you need to determine the valid starting and ending (row, column) coordinates for that specific diagonal within the matrix boundaries.
• Pay close attention to how the row and column indices change when collecting elements for an Up-Right vs. Down-Left diagonal.
• Remember to respect the matrix boundaries (0 <= r < m and 0 <= c < n) at all times.
• The total number of elements to collect is m * n. Your resulting list should contain exactly this many elements.