CMD Guide
Home › DSA › Company Practice

medium Diagonal Traverse

Problem Statement

Given a 2D matrix of size m x n, return a 1D array containing elements of the matrix in the diagonal order.

Example 1:

[[1,2,3],
 [4,5,6]]
Image
Image

Example 2:

[[1,5],
 [3,6]]

Example 3:

[[1],
 [2],
 [3]]

Try it yourself

Try solving this question here:

🎯 STRICT STANDOUT — Diagonal Traverse — problem

1. Why / judgment

Visit matrix in diagonal order alternating up-right and down-left. Diagonals are sets with constant r+c (or r−c). Simulation with direction flag and careful boundary bounce is standard; grouping by r+c then reversing alternate groups is cleaner for reasoning.

2. Big-O derivation (K11)

Must output m·n elements: Θ(mn) time, Θ(mn) output.
Grouping map O(mn) space; simulation O(1) extra besides output.

3. Pattern + when-NOT (K12)

Name: DIAGONAL SIMULATION / GROUP BY r+c

Recognition: zigzag diagonal matrix walk.

When-NOT: Only one direction diagonals → no flip. Spiral order → different boundary peel. Anti-diagonal only → r−c key.

4. Edge hand-run (K13)

1×n / m×1 trivial order.
2×2 small hand trace.
empty matrix.

5. Interviewer follow-ups (model answers)

Q1. When to flip direction?
A: After finishing a diagonal or when next cell out of bounds under current dir.

Q2. Off-by-one at corners?
A: Top-right and bottom-left need special next-step rules — prefer group-by method to avoid bugs.

Q3. Complex entries?
A: Index logic independent of values.

6. Short drills

Drill: 3×3 standard LC example.
Drill: implement both simulation and group-by.
✅ Solution Diagonal Traverse

Problem Statement

Given a 2D matrix of size m x n, return a 1D array containing elements of the matrix in the diagonal order.

Example 1:

  • Input: `matrix =
[[1, 2, 3, 4],
 [5, 6, 7, 8],
 [9, 10, 11, 12],
 [13, 14, 15, 16]]
  • Expected Output: [1, 2, 5, 9, 6, 3, 4, 7, 10, 13, 14, 11, 8, 12, 15, 16]
  • Justification: Traversal begins at 1, moves to 2, diagonally down to 5, and so on.
Image
Image

Example 2:

  • Input: matrix =
[[1,5],
 [3,6]]
  • Expected Output: [1,5,3,6]
  • Justification: The traversal starts from 1, moves to 2, then down to 3, and finally to 4.

Example 3:

  • Input: `matrix =
[[1],
 [2],
 [3]]
  • Expected Output: [1,2,3]
  • Justification: The traversal is straightforward down the single-column matrix.

Solution

To solve this problem, we need to cleverly navigate the 2D array. The key is to recognize the pattern of movement: up-right and down-left diagonals, alternating after hitting the boundaries. We utilize two pointers to track our current position in the matrix and a boolean flag to indicate the current direction of movement. This approach ensures we cover all elements in the required order.

By dynamically altering our direction at the array's boundaries, we effectively traverse all elements in the zigzag pattern. This method is efficient as it requires just a single pass through the matrix, making it a time-efficient solution. Moreover, it's intuitive as it closely follows the pattern described in the problem statement.

Step-by-step Algorithm

  • Initialize pointers for row and column, and a boolean flag for the direction of movement.
  • Iterate through the matrix elements until all elements are traversed.
    • If moving upwards:
      • Move diagonally up-right by decrementing the row and incrementing the column.
      • Check if the boundary is reached. If so, change direction and adjust row/column accordingly.
    • If moving downwards:
      • Move diagonally down-left by incrementing the row and decrementing the column.
      • Check if the boundary is reached. If so, change direction and adjust row/column accordingly.
  • Throughout the traversal, add the current element to the result list.
  • Return the result list after complete traversal.

Algorithm Walkthrough

  • Given Input: matrix =
[[1, 2, 3, 4],
 [5, 6, 7, 8],
 [9, 10, 11, 12],
 [13, 14, 15, 16]]

  1. Start: row = 0, column = 0, upwards = true, result = [].

    • Add 1. result = [1].

  2. Change diagonal: Hit boundary. Change direction. row = 0, column = 1, upwards = false.

    • Add 2. result = [1, 2].

  3. Move Down-Left: Within bounds. row = 1, column = 0.

    • Add 5. result = [1, 2, 5].

  4. Change diagonal: Hit boundary. Change direction. row = 2, column = 0, upwards = true.

    • Add 9. result = [1, 2, 5, 9].

  5. Move Up-Right: Within bounds. row = 1, column = 1.

    • Add 6. result = [1, 2, 5, 9, 6].

  6. Change diagonal: Hit boundary. Change direction. row = 0, column = 2, upwards = false.

    • Add 3. result = [1, 2, 5, 9, 6, 3].

  7. Move Down-Left: Within bounds. row = 0, column = 3.

    • Add 4. result = [1, 2, 5, 9, 6, 3, 4].

  8. Move Down-Left: Within bounds. row = 1, column = 2.

    • Add 7. result = [1, 2, 5, 9, 6, 3, 4, 7].

  9. Move Up-Right: Within bounds. row = 2, column = 1.

    • Add 10. result = [1, 2, 5, 9, 6, 3, 4, 7, 10].

  10. Change diagonal: Hit boundary. Change direction. row = 3, column = 0, upwards = false.

    • Add 13. result = [1, 2, 5, 9, 6, 3, 4, 7, 10, 13].

  11. Move Down-Left: Within bounds. row = 3, column = 1.

    • Add 14. result = [1, 2, 5, 9, 6, 3, 4, 7, 10, 13, 14].

  12. Move Down-Left: Within bounds. row = 2, column = 2.

    • Add 11. result = [1, 2, 5, 9, 6, 3, 4, 7, 10, 13, 14, 11].

  13. Change diagonal: Hit boundary. Change direction. row = 1, column = 3. upwards = false.

    • Add 8. result = [1, 2, 5, 9, 6, 3, 4, 7, 10, 13, 14, 11, 8].

  14. Move Up-Right: Within bounds. row = 3, column = 2.

    • Add 12. result = [1, 2, 5, 9, 6, 3, 4, 7, 10, 13, 14, 11, 8, 12].

  15. Change diagonal: Hit boundary. Change direction. row = 3, column = 2, upwards = true.

    • Add 15. result = [1, 2, 5, 9, 6, 3, 4, 7, 10, 13, 14, 11, 8, 12, 15].

  16. Change diagonal: Hit boundary. End of matrix. row = 3, column = 3, upwards = false.

    • Add 16. Final result = [1, 2, 5, 9, 6, 3, 4, 7, 10, 13, 14, 11, 8, 12, 15, 16].

The final output is [1, 2, 5, 9, 6, 3, 4, 7, 10, 13, 14, 11, 8, 12, 15, 16].

Code

java
import java.util.ArrayList;
import java.util.List;

public class Solution {

  public List<Integer> findDiagonalOrder(int[][] matrix) {
    List<Integer> result = new ArrayList<>();
    if (matrix == null || matrix.length == 0) return result;

    int N = matrix.length, M = matrix[0].length;
    int row = 0, column = 0;
    boolean upwards = true;

    while (row < N && column < M) {
      result.add(matrix[row][column]);

      // Determine the next cell in the traversal
      int newRow = upwards ? row - 1 : row + 1;
      int newColumn = upwards ? column + 1 : column - 1;

      // Check boundary conditions
      if (newRow < 0 || newRow == N || newColumn < 0 || newColumn == M) {
        if (upwards) {
          row += (column == M - 1) ? 1 : 0;
          column += (column < M - 1) ? 1 : 0;
        } else {
          column += (row == N - 1) ? 1 : 0;
          row += (row < N - 1) ? 1 : 0;
        }
        upwards = !upwards; // Change direction
      } else {
        row = newRow;
        column = newColumn;
      }
    }

    return result;
  }

  public static void main(String[] args) {
    Solution solution = new Solution();
    // Example 1
    int[][] matrix1 = { { 1, 5 }, { 3, 6 } };
    System.out.println(solution.findDiagonalOrder(matrix1));

    // Example 2
    int[][] matrix2 = { { 1 }, { 2 }, { 3 } };
    System.out.println(solution.findDiagonalOrder(matrix2));

    // Example 3
    int[][] matrix3 = {
      { 1, 2, 3, 4 },
      { 5, 6, 7, 8 },
      { 9, 10, 11, 12 },
      { 13, 14, 15, 16 },
    };
    System.out.println(solution.findDiagonalOrder(matrix3));
  }
}

Complexity Analysis

Time Complexity

The time complexity of the algorithm is O(M x N), where M is the number of rows, and N is the number of columns in the matrix. The algorithm traverses each element once, so the time complexity is proportional to the total number of elements, which is M x N.

Space Complexity

The space used is for the output list, which holds all elements of the matrix. Since there are M x N elements, the space complexity is O(M x N).

🎯 STRICT STANDOUT — Solution Diagonal Traverse

1. Why / judgment

Simulation: start (0,0), dir up-right; on OOB adjust position and flip. Group-by: bucket[r+c].append; iterate sums; reverse even/odd per convention. Prefer explaining group-by first — fewer boundary bugs in interviews.

2. Big-O derivation (K11)

Θ(mn).
Trace [[1,2,3],[4,5,6],[7,8,9]] → [1,2,4,7,5,3,6,8,9] classic.

3. Pattern + when-NOT (K12)

Name: DIAGONAL GROUP OR SIMULATION

Recognition: diagonal traverse.

When-NOT: Need anti-diagonal spiral hybrid → re-spec keys.

4. Edge hand-run (K13)

single row.
rectangular non-square.

5. Interviewer follow-ups (model answers)

Q1. Why reverse alternate buckets?
A: Direction zigzags each successive diagonal.

Q2. Stable order inside diagonal?
A: Decide increasing r or c consistently.

Q3. In-place?
A: Output is 1D; matrix usually read-only.

6. Short drills

Drill: 1×1, 2×3.
Drill: prove each cell once.
🧩 Pattern · Matrix

Recognize it: Grid traversal / rotation / in-place marking → index arithmetic, or DFS/BFS over cells.

▶ Visualize this problem (step it, predict each fork)
⛶ Open this problem debugger in explore mode
🤖 Don't fully get this? Learn it with Claude

Stuck on Diagonal Traverse? Open Claude, copy a block below, and it'll teach you this exact concept — visually and interactively.

🪜 Hint ladder (no spoilers)

Progressively stronger hints — you still solve it.

I'm working on the problem **Diagonal Traverse** (DSA). Give me a HINT LADDER: start with the tiniest nudge, then wait. Only reveal the next, stronger hint when I ask. Do NOT show the full solution unless I type 'show solution'. Keep me doing the thinking. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.
🎨 Explain the approach visually

See the technique, not just code.

Explain the optimal approach to **Diagonal Traverse** with a VISUAL walkthrough: trace it on a small concrete example using ASCII art / a step-by-step diagram, narrate what changes each step, then give time & space complexity with a one-line derivation. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.
🔍 Review my solution

Catch bugs, edge cases, sub-optimality.

I'll paste my solution to **Diagonal Traverse**. Review it for correctness, missed edge cases, and time/space complexity, then coach me toward the optimal — don't just rewrite it. Ask me to paste my code now. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.
🔁 Drill the pattern

Lock in recognition with look-alikes.

Give me 2 problems that use the SAME underlying pattern as **Diagonal Traverse**. For each, let me attempt first, then review my answer and name the trigger signal that reveals the pattern. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

📝 My notes

← Rotate ListFind Leaves of Binary Tree →