498. Diagonal Traverse - Detailed Explanation

Problem Statement

Given an m x n matrix, return an array of all the elements of the matrix in a diagonal order. The diagonal order means that you traverse the matrix in a zigzag pattern along its diagonals. More precisely, starting from the top-left element, you alternate between moving upward (diagonally up-right) and downward (diagonally down-left) until all elements are traversed.

Example 1

Input:

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

Output:

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

Explanation:

• Diagonal 0: Contains element [1].
• Diagonal 1: Contains elements [2, 4] → traversed upward so order becomes [2, 4].
• Diagonal 2: Contains elements [7, 5, 3] → traversed downward so order remains [7, 5, 3].
• Diagonal 3: Contains elements [6, 8] → traversed upward so order becomes [6, 8].
• Diagonal 4: Contains element [9].

When all diagonals are combined in order, we get [1, 2, 4, 7, 5, 3, 6, 8, 9].

Example 2

Input:

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

Output:

[1, 2, 3, 4]

Explanation:

• Diagonals: [1], [2, 3], [4].
  Since the second diagonal is traversed upward, it becomes [2, 3].
  Combining all gives [1, 2, 3, 4].

Constraints

• 1 ≤ matrix.length, matrix[0].length ≤ 10⁴
• The total number of elements of the matrix will not exceed 10⁴.
• The matrix elements can be any integers.

Hints

1. Zigzag Traversal:
   Notice that you alternate the direction of traversal on each diagonal. One diagonal is read from bottom to top (upward) and the next from top to bottom (downward).

2. Index Sum Grouping:
   Elements on the same diagonal share the same sum of indices (i + j). This property can be used to group elements and then reverse the order of every alternate diagonal.

3. Boundary Conditions:
   When simulating the diagonal traversal, carefully handle the matrix boundaries (i.e. when you reach the first row or the last column while moving upward, or when you reach the last row or the first column while moving downward).

Approaches

Approach 1: Simulation with Direction Toggling

Idea:
Traverse the matrix by simulating the diagonal movement. Use two variables for the current row and column and a direction flag (upward or downward). At each step, update the position accordingly. When you hit a boundary, change direction and adjust the row/column indices.

Steps:

1. Initialize row, column, and a boolean flag (for upward direction).

2. While within bounds, add the current element to the result.

3. Depending on the current direction:

   • Upward: Move up-right (row–1, col+1).
   • Downward: Move down-left (row+1, col–1).

4. When hitting a boundary, update row and col to the next valid start position and flip the direction.

Pros:

• Traverses the matrix in a single pass.
• Intuitive simulation of the movement.

Cons:

• Requires careful handling of boundary conditions.

Approach 2: Grouping by Diagonals Using Index Sum

Idea:
Every element at position (i, j) lies on the diagonal identified by the sum d = i + j. Group all elements by their diagonal index. For diagonals with an even index (or based on the traversal order), reverse the order of elements.

Steps:

1. Iterate over all elements and group them in a hash map (or list) using key = i + j.
2. For each diagonal group:
   • If the diagonal index is even, reverse the group.
3. Concatenate all groups in order of increasing diagonal index.

Pros:

• Cleaner implementation using grouping.
• Easy to understand the relation using i+j.

Cons:

• Requires extra space to hold the groups.
• Two passes over the matrix (one for grouping, one for concatenation).

Step-by-Step Walkthrough (Simulation Approach)

Consider the matrix:

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

1. Initialization:

   • Set row = 0, col = 0, directionUp = true.
   • Result list starts as empty.

2. Traverse:

   • Step 1: (0, 0): Add 1.
     Next move (upward): Attempt (–1, 1) → Out of bounds.
     Since moving upward and row becomes -1, move right to (0, 1) and flip direction.

   • Step 2: (0, 1): Add 2.
     Now direction is downward. Move down-left to (1, 0).

   • Step 3: (1, 0): Add 4.
     Continue downward: (2, –1) → Out of bounds (col -1).
     Adjust: Since col is out, move down to (2, 0) and flip direction.

   • Step 4: (2, 0): Add 7.
     Now direction is upward. Move up-right to (1, 1).

   • Step 5: (1, 1): Add 5.
     Continue upward: (0, 2).

   • Step 6: (0, 2): Add 3.
     Continue upward: (–1, 3) → Out of bounds.
     Adjust: Since row is out, move right to (0+? check boundary) – actually, when at top row and moving upward, we move to next row if col is not at the last column. Here, we are at (0,2) and col is the last column so we move down to (1,2) and flip direction.

   • Step 7: (1, 2): Add 6.
     Now direction is downward. Move down-left to (2, 1).

   • Step 8: (2, 1): Add 8.
     Continue downward: (3, 0) → Out of bounds (row becomes 3).
     Adjust: Move right to (2, 2) and flip direction.

   • Step 9: (2, 2): Add 9.

   • End traversal as all elements are covered.

3. Result:
   The result list is [1, 2, 4, 7, 5, 3, 6, 8, 9].

Code Implementation

Python Code