## Algorithm

Problem Name: 498. Diagonal Traverse

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

Constraints:

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

## Code Examples

### #1 Code Example with C++ Programming

```Code - C++ Programming```

``````
class Solution {
public:
vector<int> findDiagonalOrder(vector < vector<int>>& matrix) {
vector<int>res;
if(matrix.empty()) return res;
int m = matrix.size(), n = matrix[0].size();
vector<pair < int, int>>dir({{-1, 1}, {1, -1}});
DFS(matrix, res, 0, 0, m, n, dir, 0);
return res;
}

void DFS(vector < vector<int>>& matrix, vector<int>& res, int r, int c, int m, int n, vector < pair<int, int>>& dir, int d){
if(res.size() == m * n) return;
res.push_back(matrix[r][c]>;
int R = r + dir[d].first;
int C = c + dir[d].second;
if(R  <  0 || C < 0 || R >= m || C >= n){
d = (d + 1) % 2;
if(R < 0 || R >= m) R = r, C = c + 1;
if(C  <  0 || C >= n) R = r + 1, C = c;
}
DFS(matrix, res, R, C, m, n, dir, d);
}
};
``````
Copy The Code &

Input

cmd
mat = [[1,2,3],[4,5,6],[7,8,9]]

Output

cmd
[1,2,4,7,5,3,6,8,9]

### #2 Code Example with Java Programming

```Code - Java Programming```

``````
class Solution {
public int[] findDiagonalOrder(int[][] matrix) {
int dir = 0;
int x = 0;
int y = 0;
int numOfRows = matrix.length;
int numOfCols = matrix[0].length;
int[] ans = new int[numOfRows * numOfCols];
for (int i = 0; i  <  numOfRows * numOfCols; i++) {
ans[i] = matrix[x][y];
if ((x + y) % 2 == 0) {
if (y == numOfCols - 1) {
x++;
} else if (x == 0) {
y++;
} else {
x--;
y++;
}
} else {
if (x == numOfRows - 1) {
y++;
} else if (y == 0) {
x++;
} else {
x++;
y--;
}
}
}
return ans;
}
}
``````
Copy The Code &

Input

cmd
mat = [[1,2,3],[4,5,6],[7,8,9]]

Output

cmd
[1,2,4,7,5,3,6,8,9]

### #3 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
const findDiagonalOrder = function(matrix) {
if (!matrix.length || !matrix[0].length) {
return []
}
const m = matrix.length
const n = matrix[0].length
const output = []
for (let sum = 0; sum  < = m + n - 2; sum++) {
for (
let i = Math.min(m - 1, sum);
sum % 2 === 0 && isValid(i, sum - i, m, n);
i--
) {
const j = sum - i
output.push(matrix[i][j])
}
for (
let j = Math.min(n - 1, sum);
sum % 2 === 1 && isValid(sum - j, j, m, n);
j--
) {
const i = sum - j
output.push(matrix[i][j])
}
}
return output
}

function isValid(i, j, m, n) {
if (i < 0 || i >= m || j < 0 || j >= n) {
return false
}
return true
}
``````
Copy The Code &

Input

cmd
mat = [[1,2],[3,4]]

Output

cmd
[1,2,3,4]

### #4 Code Example with Python Programming

```Code - Python Programming```

``````
class Solution:
def findDiagonalOrder(self, matrix):
i, j, d, res, n, m = 0, 0, 1, [], len(matrix), len(matrix and matrix[0])
while i < n and j < m:
res.append(matrix[i][j])
if j + 1 < m and (i == 0 and d == 1) or (i == n - 1 and d == -1): j, d = j + 1, -d
elif i + 1 < n and (j == 0 and d == -1) or (j == m - 1 and d == 1): i, d = i + 1, -d
elif d == 1: i, j = i - 1, j + 1
else: i, j = i + 1, j - 1
return res
``````
Copy The Code &

Input

cmd
mat = [[1,2],[3,4]]

Output

cmd
[1,2,3,4]

### #5 Code Example with C# Programming

```Code - C# Programming```

``````
namespace LeetCode
{
public class _0498_DiagonalTraverse
{
public int[] FindDiagonalOrder(int[][] matrix)
{
if (matrix == null || matrix.Length == 0) return new int[0];

int N = matrix.Length;
int M = matrix[0].Length;

int[] result = new int[N * M];
int row = 0, col = 0;
for (int i = 0; i  <  result.Length; i++)
{
result[i] = matrix[row][col];
if ((row + col) % 2 == 0)
{
if (col == M - 1) { row++; }
else if (row == 0) { col++; }
else { row--; col++; }
}
else
{
if (row == N - 1) { col++; }
else if (col == 0) { row++; }
else { row++; col--; }
}
}

return result;
}
}
}
``````
Copy The Code &

Input

cmd
mat = [[1,2,3],[4,5,6],[7,8,9]]

Output

cmd
[1,2,4,7,5,3,6,8,9]