Diagonal Traverse

LeetCode 498: Diagonal Traverse Solution & Explanation

Problem Overview

TL;DR: The optimal solution simulates a zigzag path through the matrix by tracking the current direction (up-right or down-left) and adjusting indices based on boundary collisions.

The LeetCode 498 problem, titled Diagonal Traverse, requires us to linearize a 2D grid. Given an $M \times N$ matrix, we must return a single array containing all elements of the matrix traversed diagonally. The traversal starts at the top-left corner, moving up-right, then reversing to down-left upon hitting a boundary, and continuing this alternating pattern until the bottom-right corner is reached.

Brute Force Approach for Diagonal Traverse

A naive or brute force approach attempts to group elements by their diagonal properties without simulating the path step-by-step. A common observation is that for any element at matrix[i][j], the sum of indices i + j is constant across a specific diagonal.

The brute force algorithm typically follows these steps:

1. Initialize a dictionary or hash map where keys are the sums k = i + j.
2. Iterate through every element in the matrix using nested loops.
3. Append the element matrix[i][j] to the list stored at key i + j in the map.
4. Iterate through the keys from $0$ to $(M + N - 2)$.
5. If the key is even, reverse the list (to simulate the up-right direction). If odd, keep it as is (or vice versa depending on iteration order).
6. Concatenate all lists into the final result.

Why it is suboptimal: While this approach produces the correct answer, it fails to be the most efficient solution for interview contexts.

• Space Complexity: It requires additional space to store intermediate lists for every diagonal before merging them, effectively duplicating the matrix in memory before creating the result.
• Overhead: The operations of appending to dynamic lists and reversing them add unnecessary overhead compared to a direct index-manipulation approach.
• Cognitive Load: It relies on sorting or post-processing logic rather than a direct traversal, making it less intuitive as a pure matrix simulation.

Algorithm Strategy: Array/Matrix Manipulation Patterns

The strategy utilizes a direct simulation with a single pass through the matrix elements ($O(M \times N)$). We do not use auxiliary storage for sorting or grouping.

1. State Initialization: We initialize two variables, row and col, to 0. We also use a boolean or integer flag up to track the current diagonal direction (True for Up-Right, False for Down-Left).
2. Traversal Loop: We loop exactly $M \times N$ times, ensuring we process every element once.
3. Directional Logic: Inside the loop, we append the current element to our result array. Then, we calculate the next coordinates based on the current up state.
4. Boundary Enforcement:
   • If moving Up-Right: We check if we are at the right boundary first (priority is important for corners). If so, we move down one row and flip direction. Else, if we are at the top boundary, we move right one column and flip direction. Otherwise, we proceed diagonally ($r-1, c+1$).
   • If moving Down-Left: We check if we are at the bottom boundary first. If so, we move right one column and flip direction. Else, if we are at the left boundary, we move down one row and flip direction. Otherwise, we proceed diagonally ($r+1, c-1$).
5. Termination: The loop terminates naturally when the result array contains all matrix elements.

Execution Flow

1. Setup:

   • Input Matrix dimensions: $M$ rows, $N$ columns.
   • Result array res initialized to size $M \times N$.
   • Pointers r = 0, c = 0.
   • Direction up = true (start moving Up-Right).

2. Iteration (Example steps):

   • Loop i from 0 to $M \times N - 1$.
   • res[i] = matrix[r][c].

3. Coordinate Update Logic:

   • Case 1: Direction is Up-Right
     • Check Right Wall: If c == N - 1, increment r (move down), flip up to false.
     • Check Top Wall: Else if r == 0, increment c (move right), flip up to false.
     • Standard Move: Else r--, c++.
   • Case 2: Direction is Down-Left
     • Check Bottom Wall: If r == M - 1, increment c (move right), flip up to true.
     • Check Left Wall: Else if c == 0, increment r (move down), flip up to true.
     • Standard Move: Else r++, c--.

4. Completion: Return res.

Proof of Correctness

The algorithm is correct because it establishes a bijection between the steps of the loop ($0$ to $M \times N - 1$) and the coordinates of the matrix.

• Coverage: The loop runs exactly as many times as there are elements, guaranteeing complete coverage.
• Validity: The boundary checks are exhaustive. By prioritizing the "end of line" boundaries (Right wall for Up-Right, Bottom wall for Down-Left), we correctly handle the corners where two boundaries meet (e.g., Top-Right corner).
• Invariance: At the start of every iteration, (r, c) is guaranteed to be a valid index within the matrix dimensions due to the strictly controlled transitions in the previous step.

Pattern Reuse Notes

The Array/Matrix Manipulation logic used here is fundamental to several other problems.

• LeetCode 73: Set Matrix Zeroes: Uses similar row/column iteration logic, though it focuses on using the matrix itself to store state ("In-place Marking") rather than traversing a path.
• LeetCode 289: Game of Life: Requires iterating through the matrix and checking neighbor boundaries ($r-1$, $c+1$, etc.) to determine the next state, sharing the boundary-check intensity of Diagonal Traverse.

Reference Implementation

C++ Solution for LeetCode 498

1#include <vector>
2
3class Solution {
4public:
5    vector<int> findDiagonalOrder(vector<vector<int>>& mat) {
6        if (mat.empty() || mat[0].empty()) return {};
7        
8        int m = mat.size();
9        int n = mat[0].size();
10        std::vector<int> result(m * n);
11        int row = 0;
12        int col = 0;
13        bool up = true;
14        
15        for (int i = 0; i < m * n; ++i) {
16            result[i] = mat[row][col];
17            
18            if (up) {
19                if (col == n - 1) {
20                    // Hit right wall, move down
21                    row++;
22                    up = false;
23                } else if (row == 0) {
24                    // Hit top wall, move right
25                    col++;
26                    up = false;
27                } else {
28                    // Move up-right
29                    row--;
30                    col++;
31                }
32            } else {
33                if (row == m - 1) {
34                    // Hit bottom wall, move right
35                    col++;
36                    up = true;
37                } else if (col == 0) {
38                    // Hit left wall, move down
39                    row++;
40                    up = true;
41                } else {
42                    // Move down-left
43                    row++;
44                    col--;
45                }
46            }
47        }
48        
49        return result;
50    }
51};

Java Solution for LeetCode 498

1class Solution {
2    public int[] findDiagonalOrder(int[][] mat) {
3        if (mat == null || mat.length == 0) return new int[0];
4        
5        int m = mat.length;
6        int n = mat[0].length;
7        int[] result = new int[m * n];
8        int row = 0;
9        int col = 0;
10        boolean up = true;
11        
12        for (int i = 0; i < m * n; i++) {
13            result[i] = mat[row][col];
14            
15            if (up) {
16                if (col == n - 1) {
17                    // Hit right boundary; go down
18                    row++;
19                    up = false;
20                } else if (row == 0) {
21                    // Hit top boundary; go right
22                    col++;
23                    up = false;
24                } else {
25                    // Standard move up-right
26                    row--;
27                    col++;
28                }
29            } else {
30                if (row == m - 1) {
31                    // Hit bottom boundary; go right
32                    col++;
33                    up = true;
34                } else if (col == 0) {
35                    // Hit left boundary; go down
36                    row++;
37                    up = true;
38                } else {
39                    // Standard move down-left
40                    row++;
41                    col--;
42                }
43            }
44        }
45        
46        return result;
47    }
48}

Python Solution for LeetCode 498

1class Solution:
2    def findDiagonalOrder(self, mat: list[list[int]]) -> list[int]:
3        if not mat or not mat[0]:
4            return []
5            
6        m, n = len(mat), len(mat[0])
7        result = []
8        row, col = 0, 0
9        up = True
10        
11        for _ in range(m * n):
12            result.append(mat[row][col])
13            
14            if up:
15                if col == n - 1:
16                    # Hit right wall, move down
17                    row += 1
18                    up = False
19                elif row == 0:
20                    # Hit top wall, move right
21                    col += 1
22                    up = False
23                else:
24                    row -= 1
25                    col += 1
26            else:
27                if row == m - 1:
28                    # Hit bottom wall, move right
29                    col += 1
30                    up = True
31                elif col == 0:
32                    # Hit left wall, move down
33                    row += 1
34                    up = True
35                else:
36                    row += 1
37                    col -= 1
38                    
39        return result