Diagonal Traverse
Description
Given an m × n matrix mat, return all of its values in diagonal order.
The diagonals run from bottom-left to top-right, and the order takes them one after another from the top-left corner: the first is read going up and to the right, the second going down and to the left, and so on, switching direction each time.
Examples
Example 1
Input: mat = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
Output: [1, 2, 4, 7, 5, 3, 6, 8, 9]
Explanation: The diagonals r + c = 0 to 4, read up and down in turn: 1, then 2 4, then 7 5 3, then 6 8, then 9.
Example 2
Input: mat = [[1, 2], [3, 4]]
Output: [1, 2, 3, 4]
Explanation: The diagonals r + c = 0 to 2, read up and down in turn: 1, then 2 3, then 4.
Example 3
Input: mat = [[1, 2, 3, 4], [5, 6, 7, 8]]
Output: [1, 2, 5, 6, 3, 4, 7, 8]
Explanation: The diagonals r + c = 0 to 4, read up and down in turn: 1, then 2 5, then 6 3, then 4 7, then 8. With two rows, every turn is a step right: along the top row going up, along the bottom row going down.
Example 4
Input: mat = [[5], [8], [2]]
Output: [5, 8, 2]
Explanation: One column: each diagonal holds one cell, so the values come out top to bottom.
Constraints
- m == mat.length
- n == mat[i].length
- 1 ≤ m, n ≤ 10⁴
- 1 ≤ m × n ≤ 10⁴
- −10⁵ ≤ mat[i][j] ≤ 10⁵
Editorial
Brute Force
Intuition
The cells of one diagonal share r + c: going down and to the left, r grows as c shrinks. So give each diagonal a list, r + c from 0 to m + n − 2, and drop every value into its list in one pass. Filled row by row, each list holds its diagonal top row first, which is the downward order; the even diagonals go up, so read those lists backwards.
The one pass matters. Trying every row for each diagonal instead, as Introduction to Matrices does on its 3 × 4 grid, makes m × (m + n − 1) checks: 100 million on a 10,000 × 1 column, which took 7.94 s in Python where the one pass took 71 ms. The budget is 5 s for all the tests together.
Step-by-Step Explanation
Let's trace Example 1, mat = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]:
- Fill the diagonals row by row, so each gets its cells top row first: r + c = 0 gets 1, 1 gets 2 4, 2 gets 3 5 7, 3 gets 6 8 and 4 gets 9.
- Read the even ones backwards and the odd ones as they are: 1, then 2 4, then 7 5 3, then 6 8, then 9.
- That's the answer, [1, 2, 4, 7, 5, 3, 6, 8, 9].
Collect Each Diagonal, Read Every Other Backwards — Each diagonal's cells lit in turn, the even ones read backwards.
Algorithm
- Make m + n − 1 empty lists, one for each diagonal.
- Go through the cells row by row, adding each value to list
r + c. - Go through the lists in order: add the even ones to the answer backwards, the odd ones as they are.
Code
class Solution {
public:
vector<int> findDiagonalOrder(vector<vector<int>>& mat) {
int m = mat.size(), n = mat[0].size();
vector<vector<int>> diagonals(m + n - 1);
for (int r = 0; r < m; r++) // row by row: each diagonal fills top row first
for (int c = 0; c < n; c++) diagonals[r + c].push_back(mat[r][c]);
vector<int> order;
for (int d = 0; d < m + n - 1; d++) {
if (d % 2 == 0) reverse(diagonals[d].begin(), diagonals[d].end()); // the even ones go up
order.insert(order.end(), diagonals[d].begin(), diagonals[d].end());
}
return order;
}
};
class Solution:
def findDiagonalOrder(self, mat: List[List[int]]) -> List[int]:
m, n = len(mat), len(mat[0])
diagonals = [[] for _ in range(m + n - 1)]
for r in range(m): # row by row: each diagonal fills top row first
for c in range(n):
diagonals[r + c].append(mat[r][c])
order = []
for d, cells in enumerate(diagonals):
order += cells[::-1] if d % 2 == 0 else cells # the even ones go up
return order
class Solution {
public int[] findDiagonalOrder(int[][] mat) {
int m = mat.length, n = mat[0].length;
List<List<Integer>> diagonals = new ArrayList<>();
for (int d = 0; d < m + n - 1; d++) diagonals.add(new ArrayList<>());
for (int r = 0; r < m; r++) // row by row: each diagonal fills top row first
for (int c = 0; c < n; c++) diagonals.get(r + c).add(mat[r][c]);
int[] order = new int[m * n];
int k = 0;
for (int d = 0; d < m + n - 1; d++) {
List<Integer> cells = diagonals.get(d);
if (d % 2 == 0) Collections.reverse(cells); // the even ones go up
for (int v : cells) order[k++] = v;
}
return order;
}
}
var findDiagonalOrder = function(mat) {
const m = mat.length, n = mat[0].length;
const diagonals = Array.from({ length: m + n - 1 }, () => []);
for (let r = 0; r < m; r++) // row by row: each diagonal fills top row first
for (let c = 0; c < n; c++) diagonals[r + c].push(mat[r][c]);
const order = [];
diagonals.forEach((cells, d) => {
if (d % 2 === 0) cells.reverse(); // the even ones go up
order.push(...cells);
});
return order;
};
Complexity Analysis
Time Complexity: O(m × n)
Each value goes into its list once and into the answer once.
Space Complexity: O(m × n)
The lists hold every value a second time.
Why This Approach Is Not Efficient
It's linear in time already, but it keeps a second copy of the whole matrix in the lists and turns half of them round. The order can be walked directly: from each cell the next one is a step along the same diagonal, or, at an edge, a step right or down onto the next one. Whether r + c is even or odd says which way the diagonal goes.
Optimal Approach - Walk the Zigzag
Intuition
Walk the order one cell at a time. On an even diagonal (r + c even) the walk goes up and to the right, on an odd one down and to the left. When the next step would leave the matrix, move onto the next diagonal instead. Going up, that's a step down in the last column, or else a step right along the top row. Going down, it's a step right in the bottom row, or else a step down the first column.
The order of those checks matters at the corners, where both edges meet. From the top-right corner the only way on is down, and from the bottom-left one it's right, so the last-column and bottom-row checks come first.
Step-by-Step Explanation
Let's trace Example 1 again, mat = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]; the walk makes all four kinds of turn:
- 1 at (0, 0), going up: it's in the top row, so step right to (0, 1).
- 2 at (0, 1), going down: step down and to the left to (1, 0).
- 4 at (1, 0), going down: it's in the first column, so step down to (2, 0).
- 7 at (2, 0), going up: step up and to the right to (1, 1).
- 5 at (1, 1), going up: step up and to the right to (0, 2).
- 3 at (0, 2), going up: it's in the last column, so step down to (1, 2).
- 6 at (1, 2), going down: step down and to the left to (2, 1).
- 8 at (2, 1), going down: it's in the bottom row, so step right to (2, 2).
- 9 at (2, 2), going up: it's the last value, so the walk ends.
Walk the Zigzag — The walk cell by cell, turning at the edges; the cells taken so far stay lit.
Algorithm
- Start at (0, 0) with an empty answer.
- Repeat m × n times: add
mat[r][c]to the answer, then move. - If
r + cis even (going up): in the last column, step down; otherwise in the top row, step right; otherwise step up and to the right. - If
r + cis odd (going down): in the bottom row, step right; otherwise in the first column, step down; otherwise step down and to the left.
Code
class Solution {
public:
vector<int> findDiagonalOrder(vector<vector<int>>& mat) {
int m = mat.size(), n = mat[0].size();
vector<int> order;
order.reserve(m * n);
int r = 0, c = 0;
for (int i = 0; i < m * n; i++) {
order.push_back(mat[r][c]);
if ((r + c) % 2 == 0) { // going up and to the right
if (c == n - 1) r++; // the last column: step down
else if (r == 0) c++; // the top row: step right
else { r--; c++; }
} else { // going down and to the left
if (r == m - 1) c++; // the bottom row: step right
else if (c == 0) r++; // the first column: step down
else { r++; c--; }
}
}
return order;
}
};
class Solution:
def findDiagonalOrder(self, mat: List[List[int]]) -> List[int]:
m, n = len(mat), len(mat[0])
order = []
r = c = 0
for _ in range(m * n):
order.append(mat[r][c])
if (r + c) % 2 == 0: # going up and to the right
if c == n - 1: # the last column: step down
r += 1
elif r == 0: # the top row: step right
c += 1
else:
r -= 1
c += 1
else: # going down and to the left
if r == m - 1: # the bottom row: step right
c += 1
elif c == 0: # the first column: step down
r += 1
else:
r += 1
c -= 1
return order
class Solution {
public int[] findDiagonalOrder(int[][] mat) {
int m = mat.length, n = mat[0].length;
int[] order = new int[m * n];
int r = 0, c = 0;
for (int i = 0; i < m * n; i++) {
order[i] = mat[r][c];
if ((r + c) % 2 == 0) { // going up and to the right
if (c == n - 1) r++; // the last column: step down
else if (r == 0) c++; // the top row: step right
else { r--; c++; }
} else { // going down and to the left
if (r == m - 1) c++; // the bottom row: step right
else if (c == 0) r++; // the first column: step down
else { r++; c--; }
}
}
return order;
}
}
var findDiagonalOrder = function(mat) {
const m = mat.length, n = mat[0].length;
const order = [];
let r = 0, c = 0;
for (let i = 0; i < m * n; i++) {
order.push(mat[r][c]);
if ((r + c) % 2 === 0) { // going up and to the right
if (c === n - 1) r++; // the last column: step down
else if (r === 0) c++; // the top row: step right
else { r--; c++; }
} else { // going down and to the left
if (r === m - 1) c++; // the bottom row: step right
else if (c === 0) r++; // the first column: step down
else { r++; c--; }
}
}
return order;
};
Complexity Analysis
Time Complexity: O(m × n)
One step per value, each a few comparisons.
Space Complexity: O(1)
Just r and c, besides the answer itself.
Common Mistakes
Each of these looks right on a quick read, and the tests still reject it. The outputs below come from running the code.
Reading every diagonal the same way. return [v for cells in diagonals for v in cells]
On mat = [[1, 2, 3], [4, 5, 6]] it returns [1, 2, 4, 3, 5, 6]; the answer is [1, 2, 4, 5, 3, 6]. Filled row by row, each diagonal lists its cells top row first, going down and to the left. The zigzag reads every other diagonal the other way, up and to the right: r + c = 0, 2, 4 and so on come out backwards.
Checking the top row before the last column. if r == 0:
On mat = [[1, 2, 3], [4, 5, 6], [7, 8, 9]] it fails with IndexError (list index out of range) instead of returning [1, 2, 4, 7, 5, 3, 6, 8, 9]. The top-right corner is in the top row and in the last column. Going up, a walk that checks the top row first steps right, off the matrix; from the corner the only way on is down, so the last-column check has to come first.
Assuming the matrix is square. m, n = len(mat), len(mat)
On mat = [[1, 2, 3, 4], [5, 6, 7, 8]] it returns [1, 2, 5, 6]; the answer is [1, 2, 5, 6, 3, 4, 7, 8]. Diagonal Traverse takes any m × n matrix, not only squares. One size for both sides walks only the first m columns of a wide matrix, and steps past the end of a row in a tall one.
Where This Pattern Is Taught
This problem practises walking a matrix along its diagonals, where r + c stays the same, and turning at its edges. It's taught in Introduction to Matrices.