Diagonal Traverse

Medium
276.

Diagonal Traverse

Diagonal Traverse is a medium coding problem on arrays, matrix and simulation, asked in Amazon, Google, Meta and Walmart interviews.

Given an m × n matrix mat, return all its elements in diagonal order.

The traversal walks the anti-diagonals in turn, alternating direction: the first diagonal goes up-right, the second down-left, and so on.

Example 1

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

Example 2

Input
mat = [[1,2],[3,4]]
Output
[1,2,3,4]

Example 3

Input
mat = [[5]]
Output
[5]

Constraints

  • 1 <= mat.length, mat[i].length <= 8
  • -100 <= mat[i][j] <= 100
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[][]} mat
 * @return {number[]}
 */
var findDiagonalOrder = function(mat) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Diagonal Traverse — Solution in Python, Java & C++

Diagonal Traverse solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem on arrays and matrix.

Diagonal Traverse is a medium coding problem on arrays, matrix and simulation, asked in Amazon, Google, Meta and Walmart interviews.

Problem statement

Given an m × n matrix mat, return all its elements in diagonal order.

The traversal walks the anti-diagonals in turn, alternating direction: the first diagonal goes up-right, the second down-left, and so on.

Example 1

Input: mat = [[1,2,3],[4,5,6],[7,8,9]]
Output: [1,2,4,7,5,3,6,8,9]

Example 2

Input: mat = [[1,2],[3,4]]
Output: [1,2,3,4]

Example 3

Input: mat = [[5]]
Output: [5]

Constraints

  • 1 <= mat.length, mat[i].length <= 8
  • -100 <= mat[i][j] <= 100

Hints for Diagonal Traverse

  1. Hint 1

    Cells on the same anti-diagonal all share the sum r + c. Group by that sum.

  2. Hint 2

    There are rows + cols - 1 diagonals; walk them in order of that sum.

  3. Hint 3

    Reverse the direction on alternate diagonals — even sums go up-right, odd sums go down-left.

How to solve Diagonal Traverse

Cells on an anti-diagonal share r + c. Walk the rows + cols - 1 diagonals in order of that sum, going up-right on even sums and down-left on odd ones.

Approach

  1. For each d from 0 to rows + cols - 2, compute the diagonal's starting cell.
  2. Even d: start at (min(d, rows-1), d - r) and step r--, c++ while in bounds.
  3. Odd d: start at (d - c, min(d, cols-1)) and step r++, c-- while in bounds.

Why it works

Fixing r + c = d enumerates one anti-diagonal; choosing the starting corner by clamping to the grid edge handles rectangular matrices where diagonals start on the bottom or right border. Alternating direction reproduces the zigzag.

Complexity

  • Time — O(m · n)
  • Space — O(m · n) for the output

Pitfalls

  • Bucketing cells by r + c and reversing every other bucket is simpler to write and equally fast.

Reference solution

Python

def findDiagonalOrder(mat):
    rows, cols = len(mat), len(mat[0])
    out = []
    for d in range(rows + cols - 1):
        if d % 2 == 0:
            r = d if d < rows else rows - 1
            c = d - r
            while r >= 0 and c < cols:
                out.append(mat[r][c])
                r -= 1
                c += 1
        else:
            c = d if d < cols else cols - 1
            r = d - c
            while c >= 0 and r < rows:
                out.append(mat[r][c])
                r += 1
                c -= 1
    return out

Java

public static int[] findDiagonalOrder(int[][] mat) {
    int rows = mat.length, cols = mat[0].length;
    int[] out = new int[rows * cols];
    int pos = 0;
    for (int d = 0; d < rows + cols - 1; d++) {
        if (d % 2 == 0) {
            int r = d < rows ? d : rows - 1;
            int c = d - r;
            while (r >= 0 && c < cols) {
                out[pos++] = mat[r][c];
                r--;
                c++;
            }
        } else {
            int c = d < cols ? d : cols - 1;
            int r = d - c;
            while (c >= 0 && r < rows) {
                out[pos++] = mat[r][c];
                r++;
                c--;
            }
        }
    }
    return out;
}

C++

vector<int> findDiagonalOrder(vector<vector<int>>& mat) {
    int rows = (int) mat.size(), cols = (int) mat[0].size();
    vector<int> out;
    for (int d = 0; d < rows + cols - 1; d++) {
        if (d % 2 == 0) {
            int r = d < rows ? d : rows - 1;
            int c = d - r;
            while (r >= 0 && c < cols) {
                out.push_back(mat[r][c]);
                r--;
                c++;
            }
        } else {
            int c = d < cols ? d : cols - 1;
            int r = d - c;
            while (c >= 0 && r < rows) {
                out.push_back(mat[r][c]);
                r++;
                c--;
            }
        }
    }
    return out;
}

JavaScript

var findDiagonalOrder = function(mat) {
    const rows = mat.length, cols = mat[0].length;
    const out = [];
    for (let d = 0; d < rows + cols - 1; d++) {
        if (d % 2 === 0) {
            let r = d < rows ? d : rows - 1;
            let c = d - r;
            while (r >= 0 && c < cols) {
                out.push(mat[r][c]);
                r--;
                c++;
            }
        } else {
            let c = d < cols ? d : cols - 1;
            let r = d - c;
            while (c >= 0 && r < rows) {
                out.push(mat[r][c]);
                r++;
                c--;
            }
        }
    }
    return out;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Matrix and Grid Traversal