# 498. Diagonal Traverse

```
T: O(mn)
S: O(mn)
```

````java
```java
class Solution {
    public int[] findDiagonalOrder(int[][] mat) {
        int m = mat.length;
        int n = mat[0].length;
        int[] result = new int[m*n];
        int r = 0;
        int c = 0;

        for (int i = 0; i < m*n; i++) {
            result[i] = mat[r][c];
            if ((r+c)%2 == 0) {
                if (r - 1 >= 0 && c + 1 < n) {
                    r--;
                    c++;
                } else if (c + 1 < n) {
                    c++;
                } else {
                    r++;
                }
            } else {
                if (c - 1 >= 0 && r + 1 < m) {
                    r++;
                    c--;
                } else if (r + 1 < m) {
                    r++;
                } else {
                    c++;
                }
            }
        }
        return result;
    }
}

/**

00 01 10
10 11 12
20 21 22

same seq, sum is the same
filling for 0 to row*col

even sum means up
odd sum means down

so only need to consider 3 cases for each sum

even sum means up
1. can diagonal up? r - 1 >= 0 && c + 1 < n
2. c+1 < n
3. either not be able to do


odd sum means down
1. can diagonal down? c - 1 > = 0 && r + 1 < m
2. r + 1 < m
3. either not be able to do

T: O(mn)
S: O(mn)


 */
```
````
