Diagonal Traverse

Problem Statement

Given a matrix of dimensions m x n, the task is to return all elements of the matrix in a diagonal order. A diagonal order means that we start from the top-left element and proceed along the diagonals of the matrix that stretch from the bottom-left to the top-right corners. The traversal path alternates direction; originally, it moves upwards and rightwards, then switches to downwards and leftwards, continuing this pattern throughout.

Examples

Example 1

Input:

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

Output:

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

Example 2

Input:

mat = [[1,2],[3,4]]

Output:

[1,2,3,4]

Constraints

• m == mat.length
• n == mat[i].length
• 1 <= m, n <= 104
• 1 <= m * n <= 104
• -105 <= mat[i][j] <= 105

Approach and Intuition

• The matrix elements need to be read in a zig-zag diagonal fashion. This unique order starts from the top-left moving diagonally up and to the right, then switches to move down and to the left.

1. Identify the beginning and ending points of each diagonal:

   • Even indexed diagonals (0, 2, 4, ...) are traveled from bottom-left to top-right.
   • Odd indexed diagonals (1, 3, 5, ...) are traveled from top-right to bottom-left.

2. Maintain a list to store the result during the diagonal traversal.

3. Use a loop to traverse each diagonal one by one:

   • Compute the starting and ending coordinates of the current diagonal.
   • For even indexed diagonals, move upward: start with lower row index but higher column index.
   • For odd indexed diagonals, move downward: start with higher row index but lower column index.
   • Append the elements you encounter into the result list.

4. Continue this until all elements of the matrix are read in the required order.

5. Add constraints handling:

   • When moving diagonally, ensure the coordinates are valid and don't go out of the matrix bounds. This involves careful increment/decrement of row and column indices.

This approach effectively maps the unique 2D position of matrix elements to a 1D list representation, considering the alternate directions needed for each line of travel. It leverages the diagonal paths' properties to iteratively capture elements in the desired order, managing direction reversals and boundary conditions.

Solutions

class Solution {
    public int[] traverseMatrixDiagonally(int[][] grid) {
        if (grid == null || grid.length == 0) {
            return new int[0];
        }

        int rows = grid.length;
        int cols = grid[0].length;

        int r = 0, c = 0, k = 0, dir = 1;
        int[] output = new int[rows * cols];

        while (r < rows && c < cols) {
            output[k++] = grid[r][c];

            int nextRow = r + (dir == 1 ? -1 : 1);
            int nextCol = c + (dir == 1 ? 1 : -1);

            if (nextRow < 0 || nextRow == rows || nextCol < 0 || nextCol == cols) {
                if (dir == 1) {
                    r += (c == cols - 1 ? 1 : 0);
                    c += (c < cols - 1 ? 1 : 0);
                } else {
                    c += (r == rows - 1 ? 1 : 0);
                    r += (r < rows - 1 ? 1 : 0);
                }
                dir = 1 - dir;
            } else {
                r = nextRow;
                c = nextCol;
            }
        }
        return output;
    }
}