What happens if you forgetting to flip direction at boundaries?

Traversal goes out of bounds or repeats elements Fix: Add explicit checks for row and column boundaries and flip direction accordingly

What happens if you incorrect calculation of diagonal elements in brute force?

Wrong elements collected or missing elements in output Fix: Ensure row + col equals diagonal index and indices are within matrix bounds

What happens if you off-by-one errors in loops for diagonal traversal?

Index out of range exceptions or incomplete output Fix: Carefully define loop start and end indices using max and min functions

What happens if you using extra space unnecessarily in brute force?

Higher memory usage and slower performance Fix: Simulate traversal directly without intermediate storage

Interview PrepmatricesmediumAmazonGoogleFacebook

Diagonal Traverse

Choose your preparation mode4 modes available

Try It Solution Trace

🎯

Diagonal Traverse

mediumMATRIXAmazonGoogleFacebook

Imagine you have a spreadsheet and want to read its cells diagonally instead of row-wise or column-wise, like reading a zigzag pattern across the sheet.

💡 This problem requires traversing a matrix in a diagonal zigzag pattern, which is not straightforward because the direction changes after each diagonal. Beginners often struggle to keep track of indices and direction changes simultaneously.

📋

Problem Statement

Given an m x n matrix, return all elements of the matrix in a diagonal order starting from the top-left element. The traversal moves diagonally up-right and down-left alternately until all elements are visited.

1 ≤ m, n ≤ 10^4Total elements m * n ≤ 10^5

💡

Example

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

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

Traverse diagonally starting at (0,0): 1 → up-right to 2 → down-left to 4 → down-left to 7 → up-right to 5 → up-right to 3 → down-left to 6 → down-left to 8 → up-right to 9

Single element matrix → output is that element
Single row matrix → output is the row itself
Single column matrix → output is the column itself
Rectangular matrix with more rows than columns → correct zigzag traversal
Rectangular matrix with more columns than rows → correct zigzag traversal

⚠️

Common Mistakes

Forgetting to flip direction at boundaries

Traversal goes out of bounds or repeats elements

✅ Add explicit checks for row and column boundaries and flip direction accordingly

Incorrect calculation of diagonal elements in brute force

Wrong elements collected or missing elements in output

✅ Ensure row + col equals diagonal index and indices are within matrix bounds

Off-by-one errors in loops for diagonal traversal

Index out of range exceptions or incomplete output

✅ Carefully define loop start and end indices using max and min functions

Using extra space unnecessarily in brute force

Higher memory usage and slower performance

✅ Simulate traversal directly without intermediate storage

🧠

Brute Force (Simulate Each Diagonal Explicitly)

💡 This approach exists to build intuition by explicitly collecting elements diagonal by diagonal, which helps understand the traversal pattern before optimizing.

Intuition

The matrix can be traversed by iterating over each diagonal index sum (row + col) and collecting elements belonging to that diagonal. The direction alternates based on whether the diagonal index is even or odd.

Algorithm

Calculate the total number of diagonals as m + n - 1.
For each diagonal index from 0 to total diagonals - 1:
Collect all elements where row + col equals the diagonal index.
If the diagonal index is even, reverse the collected elements before adding to the result to simulate direction change.

💡 The challenge is to correctly identify elements belonging to each diagonal and reverse them on alternate diagonals to match the zigzag pattern.

</>

Code

from typing import List

def findDiagonalOrder(mat: List[List[int]]) -> List[int]:
    if not mat or not mat[0]:
        return []
    m, n = len(mat), len(mat[0])
    result = []
    for d in range(m + n - 1):
        intermediate = []
        # Determine the start row for this diagonal
        r = 0 if d < n else d - n + 1
        c = d if d < n else n - 1
        while r < m and c >= 0:
            intermediate.append(mat[r][c])
            r += 1
            c -= 1
        if d % 2 == 0:
            result.extend(intermediate[::-1])
        else:
            result.extend(intermediate)
    return result

# Driver code
if __name__ == '__main__':
    matrix = [[1,2,3],[4,5,6],[7,8,9]]
    print(findDiagonalOrder(matrix))  # Expected: [1,2,4,7,5,3,6,8,9]

Line Notes

if not mat or not mat[0]:Handle empty matrix edge case to avoid errors

for d in range(m + n - 1):Iterate over each diagonal index sum

while r < m and c >= 0:Traverse elements along the current diagonal

if d % 2 == 0:Reverse elements on even diagonals to simulate zigzag direction

import java.util.*;

public class DiagonalTraverse {
    public static int[] findDiagonalOrder(int[][] mat) {
        if (mat == null || mat.length == 0) return new int[0];
        int m = mat.length, n = mat[0].length;
        int[] result = new int[m * n];
        int index = 0;
        for (int d = 0; d < m + n - 1; d++) {
            List<Integer> intermediate = new ArrayList<>();
            int r = d < n ? 0 : d - n + 1;
            int c = d < n ? d : n - 1;
            while (r < m && c >= 0) {
                intermediate.add(mat[r][c]);
                r++;
                c--;
            }
            if (d % 2 == 0) {
                Collections.reverse(intermediate);
            }
            for (int num : intermediate) {
                result[index++] = num;
            }
        }
        return result;
    }

    public static void main(String[] args) {
        int[][] matrix = {{1,2,3},{4,5,6},{7,8,9}};
        System.out.println(Arrays.toString(findDiagonalOrder(matrix)));
    }
}

Line Notes

if (mat == null || mat.length == 0)Check for empty input to prevent errors

for (int d = 0; d < m + n - 1; d++)Loop over all diagonals by their index sum

while (r < m && c >= 0)Traverse elements along the diagonal

if (d % 2 == 0)Reverse elements on even diagonals to maintain zigzag order

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

vector<int> findDiagonalOrder(vector<vector<int>>& mat) {
    if (mat.empty() || mat[0].empty()) return {};
    int m = mat.size(), n = mat[0].size();
    vector<int> result;
    for (int d = 0; d < m + n - 1; d++) {
        vector<int> intermediate;
        int r = (d < n) ? 0 : d - n + 1;
        int c = (d < n) ? d : n - 1;
        while (r < m && c >= 0) {
            intermediate.push_back(mat[r][c]);
            r++;
            c--;
        }
        if (d % 2 == 0) {
            reverse(intermediate.begin(), intermediate.end());
        }
        result.insert(result.end(), intermediate.begin(), intermediate.end());
    }
    return result;
}

int main() {
    vector<vector<int>> matrix = {{1,2,3},{4,5,6},{7,8,9}};
    vector<int> res = findDiagonalOrder(matrix);
    for (int num : res) cout << num << " ";
    cout << endl;
    return 0;
}

Line Notes

if (mat.empty() || mat[0].empty())Guard clause for empty matrix input

for (int d = 0; d < m + n - 1; d++)Iterate over each diagonal index sum

while (r < m && c >= 0)Collect elements along the diagonal

if (d % 2 == 0)Reverse elements on even diagonals to simulate zigzag

function findDiagonalOrder(mat) {
    if (!mat || mat.length === 0) return [];
    const m = mat.length, n = mat[0].length;
    const result = [];
    for (let d = 0; d < m + n - 1; d++) {
        const intermediate = [];
        let r = d < n ? 0 : d - n + 1;
        let c = d < n ? d : n - 1;
        while (r < m && c >= 0) {
            intermediate.push(mat[r][c]);
            r++;
            c--;
        }
        if (d % 2 === 0) {
            intermediate.reverse();
        }
        result.push(...intermediate);
    }
    return result;
}

// Test
const matrix = [[1,2,3],[4,5,6],[7,8,9]];
console.log(findDiagonalOrder(matrix)); // [1,2,4,7,5,3,6,8,9]

Line Notes

if (!mat || mat.length === 0)Check for empty matrix to avoid runtime errors

for (let d = 0; d < m + n - 1; d++)Loop over each diagonal by index sum

while (r < m && c >= 0)Traverse elements along the diagonal

if (d % 2 === 0)Reverse elements on even diagonals to maintain zigzag order

⏱

Complexity

TimeO(m*n)

SpaceO(m*n)

We visit each element exactly once and store them in an output array. The intermediate list for each diagonal is at most O(min(m,n)) in size.

💡 For a 100x100 matrix, this means about 10,000 operations, which is efficient enough for medium-sized inputs.

Interview Verdict: Accepted

This approach is straightforward and accepted but can be optimized to avoid extra space for intermediate diagonals.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	`O(m*n)`	`O(m*n) extra for intermediate diagonals`	No	N/A	Mention only - never code
2. Better (Simulate Traversal)	`O(m*n)`	`O(m*n) output only`	No	N/A	Good to code if stuck on brute force
3. Optimal (Index Formula)	`O(m*n)`	`O(m*n) output only`	No	N/A	Best approach to code in interviews

Practice

(1/5)

1. Consider the following Python function that computes the sum of the diagonals of a square matrix:

def diagonalSum(mat):
    total = 0
    n = len(mat)
    for i in range(n):
        total += mat[i][i] + mat[i][n - 1 - i]
    if n % 2 == 1:
        total -= mat[n//2][n//2]
    return total

matrix = [[1,2,3],[4,5,6],[7,8,9]]
print(diagonalSum(matrix))

What is the value of total after the loop completes but before the if-condition is applied?

easy

A. 15

B. 25

C. 30

D. 45

4. The following code attempts to compute the sum of the diagonals of a square matrix. Identify the line that contains a subtle bug causing incorrect results for odd-sized matrices.

def diagonalSum(mat):
    total = 0
    n = len(mat)
    for i in range(n):
        total += mat[i][i] + mat[i][n - 1 - i]
    if n % 2 == 1:
        total += mat[n//2][n//2]  # Bug here
    return total

medium

A. Line 5: total += mat[i][i] + mat[i][n - 1 - i]

B. Line 8: total += mat[n//2][n//2] # Bug here

C. Line 7: if n % 2 == 1:

D. Line 4: for i in range(n):

Recommended

Ready to prove it?

Pass the test and this pattern moves unknown strong while earning +1 Grip toward your certificate.

10 questions~5 mineasy hard

Intuition

Algorithm

Intuition

Algorithm

Intuition

Algorithm

How to Present

Time Allocation

What the Interviewer Tests

Common Follow-ups

When to Use

Signature Phrases

NOT This Pattern When

Similar Problems

Practice

Solution

Step 1: Trace the loop iterations

Step 2: Note that the if-condition has not yet been applied

Final Answer:

Quick Check:

Solution

Step 1: Understand the problem constraints

Step 2: Evaluate approaches

Final Answer:

Quick Check:

Solution

Step 1: Identify loops and operations

Step 2: Calculate total operations

Final Answer:

Quick Check:

Solution

Step 1: Understand double counting of center element

Step 2: Identify the fix

Final Answer:

Quick Check:

Solution

Step 1: Identify space usage

Step 2: Understand common misconceptions

Final Answer:

Quick Check:

Ready to prove it?