# Diagonal Traverse

Given a matrix of M x N elements (M rows, N columns), return all elements of the matrix in diagonal order as shown in the below image.

Example:

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

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

Note:

The total number of elements of the given matrix will not exceed 10,000.

## Analysis

1. 如果 col > N, col = N-1, row = row +2;

2. 如果 row > M, row = M-1. col = col +2;

3. 如果row < 0, row = 0, 变换通道

4. 如果col < 0, col = 0, 变换通道

@shawngao

Walk Patterns:

• If out of `bottom border`(row>= m) then row = m - 1; col += 2; change walk direction.

• if out of `right border`(col >= n) then col = n - 1; row += 2; change walk direction.

• if out of `top border`(row < 0) then row = 0; change walk direction.

• if out of `left border`(col < 0) then col = 0; change walk direction.

• Otherwise, just go along with the current direction.

## Solution

``````class Solution {
public int[] findDiagonalOrder(int[][] matrix) {
if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
return new int[0];
}
int m = matrix.length;
int n = matrix[0].length;
int[] ans = new int[m * n];

int[] di = new int[]{-1, 1};
int[] dj = new int[]{1, -1};

int dir = 0;

int i = 0, j = 0;
for (int t = 0; t < m * n; t++) {
ans[t] = matrix[i][j];

i = i + di[dir];
j = j + dj[dir];

if (i >= m) {
i = m - 1;
j = j + 2;
dir = 1 - dir;
}
if (j >= n) {
j = n - 1;
i = i + 2;
dir = 1 - dir;
}
if (i < 0) {
i = 0;
dir = 1 - dir;
}
if (j < 0) {
j = 0;
dir = 1 - dir;
}
}

return ans;
}
}
``````

Intuitive Approach - 模拟移动过程

``````class Solution {
public int[] findDiagonalOrder(int[][] matrix) {
if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
return new int[0];
}

int m = matrix.length;
int n = matrix[0].length;

int[] ans = new int[m * n];

int UP = 0, DOWN = 1;
int dir = UP;

int i = 0, j = 0;

for (int k = 0; k < m * n; k++) {
ans[k] = matrix[i][j];
if (dir == UP) {
// Reaching upper bound
if (i == 0) {
if (j + 1 == n) {
i++;
} else {
j++;
}
dir = DOWN;
} else if (j + 1 == n) {
i++;
dir = DOWN;
} else {
i--;
j++;
}

} else {
if (j == 0) {
if (i + 1 == m) {
j++;
} else {
i++;
}
dir = UP;
} else if (i + 1 == m) {
j++;
dir = UP;
} else {
i++;
j--;
}
}
}
return ans;
}
}
``````

## Reference

http://fisherlei.blogspot.com/2017/07/leetcode-diagonal-traverse-solution.html

https://www.geeksforgeeks.org/zigzag-or-diagonal-traversal-of-matrix/