498. Diagonal Traverse

[mah-shamim]

Topics: Array, Matrix, Simulation

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

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

[mah-shamim]

We need to traverse a given matrix in a diagonal order, alternating the direction of traversal for each diagonal. The key observation is that the sum of the indices (i + j) for each element in a diagonal is constant. For even-indexed diagonals (by sum), we traverse from the bottom to the top, and for odd-indexed diagonals, we traverse from the top to the bottom.

Approach

1. Problem Analysis: The problem requires traversing a matrix diagonally, changing direction after each diagonal. The challenge is to handle the boundaries of the matrix correctly while alternating the traversal direction.
2. Key Insight: For each diagonal sum s (from 0 to m + n - 2), if s is even, we start from the bottom-most valid row and move upwards. If s is odd, we start from the right-most valid column and move leftwards and downwards.
3. Algorithm:
   • Iterate over each possible diagonal sum s.
   • For even s, start with the highest possible row index within bounds and move up, collecting elements until we go out of bounds.
   • For odd s, start with the highest possible column index within bounds and move down and left, collecting elements until we go out of bounds.
4. Complexity Analysis: The algorithm visits each element exactly once, resulting in a time complexity of O(m * n), which is optimal. The space complexity is O(1) excluding the output array.

Let's implement this solution in PHP: 498. Diagonal Traverse

<?php
/**
 * @param Integer[][] $mat
 * @return Integer[]
 */
function findDiagonalOrder($mat) {
    $m = count($mat);
    $n = count($mat[0]);
    $result = [];
    $maxSum = $m + $n - 2;

    for ($s = 0; $s <= $maxSum; $s++) {
        if ($s % 2 == 0) {
            $i = min($s, $m - 1);
            $j = $s - $i;
            while ($i >= 0 && $j < $n) {
                $result[] = $mat[$i][$j];
                $i--;
                $j++;
            }
        } else {
            $j = min($s, $n - 1);
            $i = $s - $j;
            while ($i < $m && $j >= 0) {
                $result[] = $mat[$i][$j];
                $i++;
                $j--;
            }
        }
    }

    return $result;
}

// Test cases
// Example 1:
$mat1 = [
    [1, 2, 3],
    [4, 5, 6],
    [7, 8, 9]
];
print_r(findDiagonalOrder($mat1));
// Expected: [1,2,4,7,5,3,6,8,9]

// Example 2:
$mat2 = [
    [1, 2],
    [3, 4]
];
print_r(findDiagonalOrder($mat2));
// Expected: [1,2,3,4]
?>

Explanation:

1. Initialization: We determine the dimensions of the matrix m (number of rows) and n (number of columns).
2. Diagonal Sum Iteration: For each diagonal sum s from 0 to m + n - 2:
   • Even s: We start from the bottom-most valid row (minimizing s and m-1) and move upwards, collecting elements until we exceed the matrix boundaries.
   • Odd s: We start from the right-most valid column (minimizing s and n-1) and move downwards and leftwards, collecting elements until we exceed the matrix boundaries.
3. Result Construction: The collected elements are stored in the result array, which is returned after processing all diagonals.

This approach efficiently collects all elements in the required diagonal order by leveraging the constant sum of indices for each diagonal and alternating traversal directions. The solution handles all edge cases, including non-square matrices, seamlessly.

[kovatz]

Thanks for solving the problem of "Diagonal Traverse"

[mah-shamim]

Thanks