Diagonal Traverse
Diagonal Traverse is a medium arrays & hashing problem solved with the matrix traversal pattern.
The best approach, optimal (direct simulation), runs in O(m · n) time and O(1) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (group by diagonal, reverse alternate) up.
Problem
Given an m x n matrix mat, return all of its elements in zigzag diagonal order.
Start at the top-left cell. Read the first anti-diagonal (cells with the same i + j) moving up and to the right, the next one moving down and to the left, and keep alternating until the bottom-right cell has been read.
Examples
Example 1
- Input
mat = [[1,2,3,4],[5,6,7,8]]- Output
[1,2,5,6,3,4,7,8]- Why
- Diagonals are read as 1 (up), 2→5 (down), 6→3 (up), 4→7 (down), 8 (up).
Example 2
- Input
mat = [[7],[8],[9]]- Output
[7,8,9]- Why
- A single column: every diagonal holds one cell, so the order is just top to bottom.
Example 3
- Input
mat = [[1,2],[3,4]]- Output
[1,2,3,4]- Why
- 1, then the anti-diagonal 2→3 going down, then 4.
Constraints
m == mat.length,n == mat[i].length1 <= m, n <= 10^4and1 <= m · n <= 10^4-10^5 <= mat[i][j] <= 10^5
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (3 examples, or your own). Submit also runs 13 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force (group by diagonal, reverse alternate) | O(m · n) | O(m · n) |
| Optimal (direct simulation) | O(m · n) | O(1) |
1Brute force (group by diagonal, reverse alternate)
O(m · n)Each cell is placed in a bucket once and copied out once.O(m · n)The buckets hold a second copy of every value.Bucket every cell by d = i + j, scanning rows top to bottom so each bucket is in top-to-bottom order. Then emit the buckets in order of d, reversing the even-indexed ones so they read upward.
- Create m + n - 1 lists; append mat[i][j] to list i + j while scanning row by row.
- For d from 0 to m + n - 2: if d is even, append the list reversed, otherwise append it as is.
class Solution {
public int[] findDiagonalOrder(int[][] mat) {
int m = mat.length, n = mat[0].length;
List<List<Integer>> buckets = new ArrayList<>();
for (int d = 0; d < m + n - 1; d++) {
buckets.add(new ArrayList<>());
}
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
buckets.get(i + j).add(mat[i][j]);
}
}
int[] result = new int[m * n];
int k = 0;
for (int d = 0; d < m + n - 1; d++) {
List<Integer> b = buckets.get(d);
if (d % 2 == 0) {
for (int t = b.size() - 1; t >= 0; t--) {
result[k++] = b.get(t);
}
} else {
for (int x : b) {
result[k++] = x;
}
}
}
return result;
}
}class Solution:
def findDiagonalOrder(self, mat: List[List[int]]) -> List[int]:
m, n = len(mat), len(mat[0])
buckets = [[] for _ in range(m + n - 1)]
for i in range(m):
for j in range(n):
buckets[i + j].append(mat[i][j])
result = []
for d in range(m + n - 1):
if d % 2 == 0:
result.extend(reversed(buckets[d]))
else:
result.extend(buckets[d])
return resultclass Solution {
public:
vector<int> findDiagonalOrder(vector<vector<int>>& mat) {
int m = mat.size(), n = mat[0].size();
vector<vector<int>> buckets(m + n - 1);
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
buckets[i + j].push_back(mat[i][j]);
vector<int> result;
result.reserve(m * n);
for (int d = 0; d < m + n - 1; d++) {
if (d % 2 == 0)
result.insert(result.end(), buckets[d].rbegin(), buckets[d].rend());
else
result.insert(result.end(), buckets[d].begin(), buckets[d].end());
}
return result;
}
};function findDiagonalOrder(mat) {
const m = mat.length, n = mat[0].length;
const buckets = Array.from({ length: m + n - 1 }, () => []);
for (let i = 0; i < m; i++)
for (let j = 0; j < n; j++)
buckets[i + j].push(mat[i][j]);
const result = [];
for (let d = 0; d < m + n - 1; d++) {
const b = buckets[d];
if (d % 2 === 0) {
for (let t = b.length - 1; t >= 0; t--) result.push(b[t]);
} else {
for (const x of b) result.push(x);
}
}
return result;
}2Optimal (direct simulation)
O(m · n)Each cell is visited exactly once with O(1) work per step.O(1)Only the position and direction are stored (output not counted).Walk the matrix cell by cell with a direction flag. Going up, move to (i - 1, j + 1); going down, move to (i + 1, j - 1). When the next step would leave the matrix, slide along the border instead (right or down when going up, down or right when going down) and flip the direction. Checking the far border first handles the corners.
- i = j = 0, up = true; repeat m · n times: write mat[i][j].
- If up: if j == n - 1, go down a row (i++) and flip; else if i == 0, go right (j++) and flip; else i--, j++.
- If down: if i == m - 1, go right (j++) and flip; else if j == 0, go down (i++) and flip; else i++, j--.
class Solution {
public int[] findDiagonalOrder(int[][] mat) {
int m = mat.length, n = mat[0].length;
int[] result = new int[m * n];
int i = 0, j = 0;
boolean up = true;
for (int k = 0; k < m * n; k++) {
result[k] = mat[i][j];
if (up) {
if (j == n - 1) { i++; up = false; }
else if (i == 0) { j++; up = false; }
else { i--; j++; }
} else {
if (i == m - 1) { j++; up = true; }
else if (j == 0) { i++; up = true; }
else { i++; j--; }
}
}
return result;
}
}class Solution:
def findDiagonalOrder(self, mat: List[List[int]]) -> List[int]:
m, n = len(mat), len(mat[0])
result = [0] * (m * n)
i = j = 0
up = True
for k in range(m * n):
result[k] = mat[i][j]
if up:
if j == n - 1:
i += 1
up = False
elif i == 0:
j += 1
up = False
else:
i -= 1
j += 1
else:
if i == m - 1:
j += 1
up = True
elif j == 0:
i += 1
up = True
else:
i += 1
j -= 1
return resultclass Solution {
public:
vector<int> findDiagonalOrder(vector<vector<int>>& mat) {
int m = mat.size(), n = mat[0].size();
vector<int> result(m * n);
int i = 0, j = 0;
bool up = true;
for (int k = 0; k < m * n; k++) {
result[k] = mat[i][j];
if (up) {
if (j == n - 1) { i++; up = false; }
else if (i == 0) { j++; up = false; }
else { i--; j++; }
} else {
if (i == m - 1) { j++; up = true; }
else if (j == 0) { i++; up = true; }
else { i++; j--; }
}
}
return result;
}
};function findDiagonalOrder(mat) {
const m = mat.length, n = mat[0].length;
const result = new Array(m * n);
let i = 0, j = 0, up = true;
for (let k = 0; k < m * n; k++) {
result[k] = mat[i][j];
if (up) {
if (j === n - 1) { i++; up = false; }
else if (i === 0) { j++; up = false; }
else { i--; j++; }
} else {
if (i === m - 1) { j++; up = true; }
else if (j === 0) { i++; up = true; }
else { i++; j--; }
}
}
return result;
}Edge cases to test
- A single cell
- A single row or a single column
- Wide matrices (n much larger than m) and tall ones (m much larger than n)
- Turning at a corner, where both the row and the column hit a border at once
Hints
Hint 1
All cells on one anti-diagonal share the same i + j. There are m + n - 1 such diagonals.
Hint 2
Diagonals with an even index are read going up-right (row decreasing); odd ones going down-left.
Hint 3
You can also walk the matrix directly: move up-right until you fall off, then decide whether to step right or down, flip the direction, and continue.
FAQ
What is the best time complexity for Diagonal Traverse?
Optimal (direct simulation) runs in O(m · n) time and O(1) extra space. Each cell is visited exactly once with O(1) work per step.
Which pattern does Diagonal Traverse use?
It is a arrays & hashing problem that uses the matrix traversal pattern. Other problems with the same pattern: Spiral Matrix, Best Meeting Point, Sparse Matrix Multiplication.
Is there a brute force solution for Diagonal Traverse?
Yes. Brute force (group by diagonal, reverse alternate) takes O(m · n) time and O(m · n) space. Bucket every cell by d = i + j, scanning rows top to bottom so each bucket is in top-to-bottom order.
Which edge cases should I test for Diagonal Traverse?
A single cell; A single row or a single column; Wide matrices (n much larger than m) and tall ones (m much larger than n); Turning at a corner, where both the row and the column hit a border at once.