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.
- Difficulty: Medium
- Topics: Arrays, Matrix, Simulation
- Asked at: Amazon, Google, Meta, Walmart
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
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
Hint 1
Cells on the same anti-diagonal all share the sum
r + c. Group by that sum.Hint 2
There are
rows + cols - 1diagonals; walk them in order of that sum.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
- For each
dfrom 0 torows + cols - 2, compute the diagonal's starting cell. - Even
d: start at(min(d, rows-1), d - r)and stepr--, c++while in bounds. - Odd
d: start at(d - c, min(d, cols-1))and stepr++, 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 + cand 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 outJava
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