498. Diagonal Traverse

JIAKAOBO

LeetCode

感谢赞助!

• ㊗️
• 大家
• offer
• 多多！

Problem

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 <= 10^4
• 1 <= m * n <= 10^4
• -10^5 <= mat[i][j] <= 10^5

Code

class Solution {
    public int[] findDiagonalOrder(int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;

        int[] res = new int[m * n];
        int row = 0;
        int col = 0;
        int d = 1;

        for (int i = 0; i < m * n; i++) {
            res[i] = matrix[row][col];
            row -= d;
            col += d;

            if (row >= m) {
                row = m - 1; 
                col += 2; 
                d = - d;
            }
            
            if (col >= n) { 
                col = n - 1; 
                row += 2; 
                d = - d;
            }
            
            if (row < 0)  { 
                row = 0; 
                d = - d;
            }
            
            if (col < 0)  { 
                col = 0; 
                d = - d;
            }
        }

        return res;
    }
}