# Diagonal Traverse
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/diagonal-traverse)
Canonical: https://scaleengineer.com/dsa/problems/diagonal-traverse
**Data structures:** Array, Matrix
**Companies:** [Roblox](https://scaleengineer.com/companies/roblox), [Zoho](https://scaleengineer.com/companies/zoho), [Nike](https://scaleengineer.com/companies/nike), [Nykaa](https://scaleengineer.com/companies/nykaa), [Liftoff](https://scaleengineer.com/companies/liftoff)
---
## Problem
Given an `m x n` matrix `mat`, return _an array of all the elements of the array in a diagonal order_.

**Example 1:**

![](https://assets.glich.co/dsa/diagonal-traverse/image0.jpg) 

**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]

**Constraints:**

* `m == mat.length`
* `n == mat[i].length`
* `1 <= m, n <= 104`
* `1 <= m * n <= 104`
* `-105 <= mat[i][j] <= 105`

# Approaches
## Group by Diagonals
This approach is based on the observation that all elements on the same diagonal have a constant sum of their row and column indices (`i + j`). We can use this property to group elements by their diagonal. First, we iterate through the matrix and store each element in a hash map, where the key is the sum of indices `i + j` and the value is a list of elements on that diagonal. After grouping, we iterate through the diagonals in increasing order of their index sum. For diagonals with an even index sum, the traversal direction is up-right, so we reverse the corresponding list of elements. For odd index sums, the direction is down-left, and the order is already correct. We then append these lists in order to form the final result.
**Time:** O(M * N). We iterate through the matrix once to populate the map (O(M*N)). Then, we iterate through the map's values to build the result. The total number of elements is M*N, and operations like reversing and adding them to the result list take O(M*N) time in total. · **Space:** O(M * N), where M is the number of rows and N is the number of columns. This is because we store all the elements of the matrix in the `diagonals` map.
**Pros:** The logic is straightforward and easy to reason about.; Separates the problem into two distinct steps: grouping and ordering.
**Cons:** Requires O(M * N) extra space to store all the matrix elements in an intermediate data structure, which is inefficient for large matrices.
### Explanation
```java
class Solution {
    public int[] findDiagonalOrder(int[][] mat) {
        if (mat == null || mat.length == 0) {
            return new int[0];
        }
        int m = mat.length;
        int n = mat[0].length;
        // The maximum sum of indices is (m-1) + (n-1)
        Map<Integer, List<Integer>> diagonals = new HashMap<>();

        // Group elements by diagonal sum (i + j)
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                int key = i + j;
                diagonals.putIfAbsent(key, new ArrayList<>());
                diagonals.get(key).add(mat[i][j]);
            }
        }

        List<Integer> resultList = new ArrayList<>();
        // Construct the result array by processing diagonals
        for (int key = 0; key <= (m - 1) + (n - 1); key++) {
            List<Integer> diagonal = diagonals.get(key);
            // For even-sum diagonals, traverse upwards (reverse order)
            if (key % 2 == 0) {
                Collections.reverse(diagonal);
            }
            resultList.addAll(diagonal);
        }

        // Convert List<Integer> to int[]
        int[] result = new int[m * n];
        for (int i = 0; i < resultList.size(); i++) {
            result[i] = resultList.get(i);
        }
        return result;
    }
}
```
### Algorithm
1. Initialize a map, `diagonals`, where the key is an integer representing the diagonal index (sum of row and column indices) and the value is a list of integers on that diagonal.
2. Iterate through the input matrix `mat` from row `i = 0` to `m-1` and column `j = 0` to `n-1`.
3. For each element `mat[i][j]`, calculate its diagonal index `d = i + j`.
4. Add the element `mat[i][j]` to the list associated with key `d` in the `diagonals` map. If the key doesn't exist, create a new list.
5. After populating the map, initialize an empty list `resultList` to store the final flattened elements.
6. Iterate through the diagonals by their index `d` from `0` up to `m + n - 2`.
7. For each diagonal `d`, retrieve the list of its elements from the map.
8. If the diagonal index `d` is even, the traversal is up-right. This means the elements should be in the reverse order of how they were added (which was top-to-bottom). Therefore, reverse the list of elements for this diagonal.
9. Append the elements of the (possibly reversed) list to `resultList`.
10. Finally, convert the `resultList` into an integer array and return it.

## Direct Simulation
A more efficient approach is to directly simulate the traversal path without using any extra space (besides the output array). We can iterate through the matrix, placing elements into our result array one by one. We maintain the current `(row, col)` position and determine the next move based on the current direction and boundary conditions. The direction of traversal (up-right or down-left) alternates. A clever way to manage the direction is by observing that the sum of indices `row + col` is even for all cells in up-right moving diagonals and odd for all cells in down-left moving diagonals. This simplifies the logic for determining the next move at each step.
**Time:** O(M * N). We traverse each of the M * N elements of the matrix exactly once, and the work done at each step is constant. · **Space:** O(1). The space required for the output array is not considered extra space. The variables used for tracking position and dimensions take up constant space.
**Pros:** Extremely space-efficient, using only O(1) extra space.; Solves the problem in a single pass over the matrix elements.
**Cons:** The logic for handling boundary conditions and direction changes can be complex and requires careful implementation to avoid errors.
### Explanation
```java
class Solution {
    public int[] findDiagonalOrder(int[][] mat) {
        if (mat == null || mat.length == 0) {
            return new int[0];
        }

        int m = mat.length;
        int n = mat[0].length;
        int[] result = new int[m * n];
        int row = 0, col = 0;

        for (int i = 0; i < result.length; i++) {
            result[i] = mat[row][col];
            
            // Direction is up-right if (row + col) is even
            if ((row + col) % 2 == 0) { 
                if (col == n - 1) {
                    // Hit right wall, must move down
                    row++;
                } else if (row == 0) {
                    // Hit top wall, must move right
                    col++;
                } else {
                    // In-bounds, move up-right
                    row--;
                    col++;
                }
            } else { // Direction is down-left
                if (row == m - 1) {
                    // Hit bottom wall, must move right
                    col++;
                } else if (col == 0) {
                    // Hit left wall, must move down
                    row++;
                } else {
                    // In-bounds, move down-left
                    row++;
                    col--;
                }
            }
        }
        return result;
    }
}
```
### Algorithm
1. Handle the edge case of an empty or null matrix.
2. Get the matrix dimensions, `m` and `n`.
3. Initialize an integer array `result` of size `m * n` to store the output.
4. Initialize the current position pointers `row = 0` and `col = 0`.
5. Loop `m * n` times, once for each element in the matrix.
6. In each iteration, add the element `mat[row][col]` to the `result` array.
7. Determine the next position by checking the current direction, which can be inferred from the sum `row + col`.
8. If `(row + col)` is even, the direction is up-right:
    - If at the right boundary (`col == n - 1`), move down to the next diagonal: `row++`.
    - If at the top boundary (`row == 0`), move right to the next diagonal: `col++`.
    - Otherwise, move diagonally up-right: `row--`, `col++`.
9. If `(row + col)` is odd, the direction is down-left:
    - If at the bottom boundary (`row == m - 1`), move right to the next diagonal: `col++`.
    - If at the left boundary (`col == 0`), move down to the next diagonal: `row++`.
    - Otherwise, move diagonally down-left: `row++`, `col--`.
10. After the loop completes, return the `result` array.

# Solutions
### Java

```java
class Solution {
public
  int[] findDiagonalOrder(int[][] mat) {
    int m = mat.length, n = mat[0].length;
    int[] ans = new int[m * n];
    int idx = 0;
    List<Integer> t = new ArrayList<>();
    for (int k = 0; k < m + n - 1; ++k) {
      int i = k < n ? 0 : k - n + 1;
      int j = k < n ? k : n - 1;
      while (i < m && j >= 0) {
        t.add(mat[i][j]);
        ++i;
        --j;
      }
      if (k % 2 == 0) {
        Collections.reverse(t);
      }
      for (int v : t) {
        ans[idx++] = v;
      }
      t.clear();
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  vector<int> findDiagonalOrder(vector<vector<int>> &mat) {
    int m = mat.size(), n = mat[0].size();
    vector<int> ans;
    vector<int> t;
    for (int k = 0; k < m + n - 1; ++k) {
      int i = k < n ? 0 : k - n + 1;
      int j = k < n ? k : n - 1;
      while (i < m && j >= 0)
        t.push_back(mat[i++][j--]);
      if (k % 2 == 0)
        reverse(t.begin(), t.end());
      for (int &v : t)
        ans.push_back(v);
      t.clear();
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def findDiagonalOrder(self, mat: List[List[int]]) -> List[int]: m, n = len(mat), len(mat[0]) ans = [] for k in range(m + n - 1): t = [] i = 0 if k < n else k - n + 1 j = k if k < n else n - 1 while i < m and j >= 0: t . append(mat[i][j]) i += 1 j -= 1 if k % 2 == 0: t = t[:: - 1] ans . extend(t) return ans

```