# 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

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

在上升通道的时候， row = row -1, col = col +1

在下降通道的时候，row = row +1, col = col -1

![](https://1611446478-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M63nDeIUEfibnkE8C6W%2Fsync%2F54c4739d5da0dea5b5cb89a631c6b002fe5cb1c7.png?generation=1588144785114656\&alt=media)

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](https://leetcode.com/problems/diagonal-traverse/discuss/97712/Concise-Java-Solution)

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.

直接模拟扫描过程，分类UP，DOWN的移动方向，再对上下左右边界（以及左下，右上定点）进行判断。

## Solution

```java
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 - 模拟移动过程

```java
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/>