The O(n) Club: Diagonal Traverse — How to Survive the Matrix Zigzag Gauntlet

The O(n) Club: Diagonal Traverse — How to Survive the Matrix Zigzag Gauntlet

⚡ TL;DR

Zigzag through every element of a 2D matrix by diagonals. If your brain defaulted to a brute-force mess, you’re not alone. Here’s what that typically looks like in Java:

// Brute force? Oh no...
List<Integer> result = new ArrayList<>();
for (int k = 0; k < m + n - 1; k++) {
    List<Integer> diag = new ArrayList<>();
    for (int i = 0; i < m; i++) {
        int j = k - i;
        if (j >= 0 && j < n) diag.add(matrix[i][j]);
    }
    if (k % 2 == 0) Collections.reverse(diag);
    result.addAll(diag);
}

🧠 How Devs Usually Mess This Up

If you’ve ever spent an hour staring at your output thinking, “Did that diagonal just moonwalk?” you’re in good company. Most devs get directionality wrong (hello, backwards diagonals), believe all matrices are romantic perfect squares, or declare a truce with off-by-one errors. Spoiler: matrices start at index zero whether you like it or not, and diagonals do not care about your feelings.

🔍 What’s Actually Going On

This problem is less Tron, more Pac-Man: diagonals are identified by the sum k = i + j. Upwards or downwards motion? That depends if k is even or odd. Even diagonals need to be reversed after you collect them because they’re traversed the wrong way by default (another designer’s idea of a hilarious prank). Boundaries matter—don’t run face first into the matrix wall! If you do: change where you start the next diagonal.

🛠️ PseudoCode

• Let m = matrix.length and n = matrix[0].length.
• For each diagonal index k = 0 to m + n - 2:
  • If k < n: start at (row=0, col=k).
  • Else: start at (row=k-n+1, col=n-1).
• While row = 0:
  • Add matrix[row][col] to a temporary list.
  • Increment row, decrement col (march down-left).
• If diagonal is even-numbered, reverse list before adding to result.
• Slap everything together into your answer array.

💻 The Code

public int[] findDiagonalOrder(int[][] matrix) {
    if (matrix == null || matrix.length == 0) return new int[0];
    int m = matrix.length, n = matrix[0].length;
    int[] res = new int[m * n];
    int idx = 0;
    for (int k = 0; k < m + n - 1; k++) {
        int row = k < n ? 0 : k - n + 1;
        int col = k < n ? k : n - 1;
        List<Integer> diagonal = new ArrayList<>();
        while (row < m && col >= 0) {
            diagonal.add(matrix[row][col]);
            row++;
            col--;
        }
        if (k % 2 == 0) Collections.reverse(diagonal);
        for (int num : diagonal) res[idx++] = num;
    }
    return res;
}

⚠️ Pitfalls, Traps & Runtime Smacks

• Non-square matrix confusion: Your code must work on rectangles. Surprise!
• Boundary mayhem: Touching the edge? Change starting point. Don’t ask why, just do.
• Even diagonal = reverse or regret: Miss this, and your output will look like the matrix tripped over itself.
• Time & space: It’s O(mn) overall, a brief O(d) per diagonal for reversal. Unless you’re traversing the Hubble Space Telescope’s sensor array, you’re fine.

🧠 Interviewer Brain-Tattoo

If you remember nothing else: “Odd diagonals go with the flow; even ones go against traffic. Just like real life in tech.”