Diagonal Traverse
Medium · Arrays & Hashing · Explanation and code example
Alternating Diagonal Walk
How it works
Move up-right on one diagonal and down-left on the next. After emitting a cell, advance in the current direction and correct any crossed matrix boundary, flipping direction. Carefully ordered boundary corrections handle rectangular matrices as well as squares.
Steps
- Start at the top-left cell moving up-right.
- Emit each cell and advance diagonally.
- Correct row/column overflow and switch direction until rows × columns values are emitted.
Complexity
- Time: O(rows × columns).
- Space: O(rows × columns) output and O(1) extra workspace.
Things to watch for
- The correction order matters when a move crosses two bounds.
- Check single-row and single-column matrices.
- The traversal visits cells, rather than sorting by their values.
Python code example
class Solution:
def findDiagonalOrder(self, mat: list[list[int]]) -> list[int]:
m, n = len(mat), len(mat[0])
result, direction, row, col = [], 1, 0, 0
for _ in range(m * n):
result.append(mat[row][col])
row -= direction
col += direction
if row == m:
row = m - 1
col += 2
direction = -direction
if col == n:
col = n - 1
row += 2
direction = -direction
if row < 0:
row = 0
direction = -direction
if col < 0:
col = 0
direction = -direction
return result
C++ code example
class Solution {
public:
vector<int> findDiagonalOrder(vector<vector<int>>& matrix) {
const int m = matrix.size();
const int n = matrix[0].size();
vector<int> ans(m * n);
int d = 1; // left-bottom -> right-top
int row = 0;
int col = 0;
for (int i = 0; i < m * n; ++i) {
ans[i] = matrix[row][col];
row -= d;
col += d;
// out-of-bounds
if (row == m)
row = m - 1, col += 2, d = -d;
if (col == n)
col = n - 1, row += 2, d = -d;
if (row < 0)
row = 0, d = -d;
if (col < 0)
col = 0, d = -d;
}
return ans;
}
};
Source and license
Explanation by LC Tracker. Code adapted from walkccc / Peng-Yu Chen · MIT license. Node types are supplied by LeetCode where needed.