Description

Given m x n matrix mat, return an array of all elements of array in a diagonal order.

Example 1

1        1 2 3
2        4 5 6
3        7 8 9
4
5Input: mat = [[1,2,3],[4,5,6],[7,8,9]]
6Output: [1,2,4,7,5,3,6,8,9]

Example 2:

1Input: mat = [[1,2],[3,4]]
2Output: [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

Solution

This is plain iteration problem with some conditionals. If we look at the pattern carefully, we can see that the direction changes from up to down at the edges and vice a versa. So, we have to have those as conditionals and we can iterate through all elements of the arrray.

 1class Solution {
 2    public int[] findDiagonalOrder(int[][] matrix) {
 3        int rows = matrix.length;
 4        int cols = matrix[0].length;
 5        int[] result = new int[rows * cols];
 6        int i = 0; // keep track of rows
 7        int j = 0; // keep track of columns
 8        int k = 0; // index for inserting into new array
 9        boolean up = true; // toggle to decided if we need to move up or down
10        while (k < rows * cols) {
11            result[k++] = matrix[i][j];
12            if (up) {
13                if (j == cols - 1) {
14                    up = false;
15                    i++;
16                } else if (i == 0) {
17                    up = false;
18                    j++;
19                }  else if (i == rows - 1 || j == 0) {
20                    up = true;
21                    j++;
22                    i--;
23                } else {
24                    i--;
25                    j++;
26                }
27            } else {
28                if (i == rows - 1) {
29                    up = true;
30                    j++;
31                } else if (j == 0) {
32                    i++;
33                    up = true;
34                }else {
35                    i++;
36                    j--;
37                }
38            }
39        }
40        return result;
41    }
42}