Formatted question description: https://leetcode.ca/all/498.html

498. Diagonal Traverse

Level

Medium

Description

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]

Explanation:

Image text

Note:

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

Solution

The most difficult point is to determine which is the next element. If a border of the matrix is met, then the next element is always to the down or to the right. Consider the cases where each border is met and obtain the next element accordingly.

public class Solution {
    public int[] findDiagonalOrder(int[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0)
            return new int[0];
        int rows = matrix.length, columns = matrix[0].length;
        int totalElements = rows * columns;
        int[] order = new int[totalElements];
        int vertical = -1, horizontal = 1;
        int row = 0, column = 0;
        for (int i = 0; i < totalElements; i++) {
            order[i] = matrix[row][column];
            row += vertical;
            column += horizontal;
            if (row < 0 && column >= columns) {
                row = 1;
                column = columns - 1;
                vertical = 1;
                horizontal = -1;
            } else if (row >= rows && column < 0) {
                row = rows - 1;
                column = 1;
                vertical = -1;
                horizontal = 1;
            } else if (row < 0) {
                row = 0;
                vertical = 1;
                horizontal = -1;
            } else if (row >= rows) {
                row = rows - 1;
                column += 2;
                vertical = -1;
                horizontal = 1;
            } else if (column < 0) {
                column = 0;
                vertical = -1;
                horizontal = 1;
            } else if (column >= columns) {
                column = columns - 1;
                row += 2;
                vertical = 1;
                horizontal = -1;
            }
        }
        return order;
    }
}

All Problems

All Solutions