261. Diagonal Traverse

Cells on the same diagonal share the sum r + c. Iterate diagonals 0..m+n-2, walking up-right on even diagonals and down-left on odd ones.

Diagonals by r + c

Every anti-diagonal has a constant r + c = d. Iterate d from 0 to m+n-2:

• Even d: traverse up-right (r decreasing, c increasing), starting from the lowest valid row.
• Odd d: traverse down-left (r increasing, c decreasing), starting from the rightmost valid column.

This produces the zig-zag diagonal order.

Worked example

[[1,2,3],[4,5,6],[7,8,9]] → [1,2,4,7,5,3,6,8,9].

Complexity

• Time: O(m·n).
• Space: O(1) extra.

class Solution {
    public int[] findDiagonalOrder(int[][] mat) {
        if (mat.length == 0 || mat[0].length == 0) return new int[0];
        int m = mat.length, n = mat[0].length;
        int[] res = new int[m * n];
        int idx = 0;
        for (int d = 0; d < m + n - 1; d++) {
            if (d % 2 == 0) {
                int r = Math.min(d, m - 1), c = d - r;
                while (r >= 0 && c < n) {
                    res[idx++] = mat[r][c];
                    r--;
                    c++;
                }
            } else {
                int c = Math.min(d, n - 1), r = d - c;
                while (c >= 0 && r < m) {
                    res[idx++] = mat[r][c];
                    r++;
                    c--;
                }
            }
        }
        return res;
    }
}