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

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.

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

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/