# 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]

Explanation:
```

![](https://1817027152-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M97UlEWvq7aSC1s7hjT%2F-MCB3vMoNoGsCv1v7Cok%2F-MCB5_XRT72zY9XsvCJZ%2Fimage.png?alt=media\&token=d9bafe96-6e74-4344-a1f7-379061b06dcf)

**Note:**

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

```java
public class Solution {
    public int[] findDiagonalOrder(int[][] matrix) {
        if (matrix.length == 0)
            return new int[0];
        int r = 0, c = 0, m = matrix.length, n = matrix[0].length, arr[] = new int[m * n];
        for (int i = 0; i < m * n; i++) {
            arr[i] = matrix[r][c];
            if ((r + c) % 2 == 0) { // moving up
                if (c == n - 1)
                    r++;
                else if (r == 0)
                    c++;
                else {
                    r--;
                    c++;
                }
            } else { // moving down
                if (r == m - 1)
                    c++;
                else if (c == 0)
                    r++;
                else {
                    r++;
                    c--;
                }
            }
        }
        return arr;
    }
}
```
