Diagonal Traverse Solution In C++/Python/java/JS
Problem Description
Given an m x n matrix mat, return an array of all the elements of the array in a diagonal order.
Example
Input: mat = [[1,2,3],[4,5,6],[7,8,9]]
Output: [1,2,4,7,5,3,6,8,9]
Explanation: We pick elements diagonally. First 1, then 2 and 4, then 7, 5, 3, and so on, collecting numbers as we move through the matrix in a zig-zag pattern.
Input: mat = [[1,2],[3,4]]
Output: [1,2,3,4]
Explanation: We collect elements starting with 1, then move diagonally to 2, then 3, then 4, covering all elements in diagonal order.
Constraints
- m == mat.length
- n == mat[i].length
- 1 <= m, n <= 104
- 1 <= m * n <= 104
- -105 <= mat[i][j] <= 105
Figuring out "Diagonal Traverse" can be solved using different approaches. We will first figure out the most intuitive approach and move to the optimal approach if exists. Let's sit with a pen and paper and figure out the algorithm !!
Optimal Approach
Intuition
We’ve got this problem where we’re given a 2D matrix filled with integers. Our goal is to return all the elements of this matrix, but not in the usual row-by-row or column-by-column fashion. Instead, we need to walk through it diagonally — starting from the top-left, we go up-right, then down-left, then up-right again, and keep zigzagging like that until we’ve visited every cell.
Let us take an example matrix so that we can internalize the mechanics clearly:
mat:
[[1, 2, 3, 4],
[5, 6, 7, 8],
[9, 10, 11, 12]]
Now, we are asked to traverse this matrix diagonally. So, the first question we must clarify is:
What does it mean to traverse diagonally in this context?
We are not referring to a single fixed direction here. The traversal alternates between two patterns:
- First, we move up-right.
- Then, we switch and move down-left.
- Then up-right again, and so on.
This creates a zigzag pattern along the diagonals. To better understand this, we should simulate it manually.
Let us simulate this step by step. What would we pick first?
We begin at the top-left corner, which is mat[0][0] = 1.
From here, the first direction is up-right:
- We attempt to go to mat[-1][1], but row -1 is out of bounds.
- Therefore, we have reached the top boundary.
Now we must decide where the next diagonal begins. Since we were moving up-right and hit the top, the rule is:
If we are at the top row, what should be our next move?
→ We move right, if possible. So we go to mat[0][1] = 2.
From this position, we switch direction. Now we go down-left.
How do we move along this diagonal?
When moving down-left, our direction vector is:
row += 1, col -= 1.
So, we proceed:
- From mat[0][1] = 2 to mat[1][0] = 5
- Then attempt mat[2][-1], which is invalid — column -1 is out of bounds. We have hit the left boundary.
Now what should we do?
If we are at the left boundary, where should the next diagonal begin?
→ We move down, if possible. So from mat[2][0] = 9, we switch direction again and go up-right.
What pattern are we seeing?
Each time we finish walking a diagonal, two decisions must be made:
- Where is the new starting point (the “head” of the next diagonal)?
- What is the new direction?
Toggling direction is simple. A boolean variable can manage that. However, determining the next valid head requires careful boundary checks.
How do we figure out the next diagonal head?
Let us formalize the rule set we have inferred:
If we are moving up-right:
- If we exit the top of the matrix:
- And we are in the last column, then we cannot move right → so we move down.
- Otherwise, we move right.
If we are moving down-left:
- If we exit the matrix:
- And we are in the last row, then we cannot move down → so we move right.
- Otherwise, we move down.
This logic gives us the correct entry point for the next diagonal, after one finishes.
In summary
- We move along the current diagonal (up-right or down-left)
- We detect and handle when we go out of bounds
- We jump to the correct next head
- We toggle the direction
Thought Exercise
We might ask ourselves:
“Why not collect each diagonal in a temporary list and reverse it conditionally?”
That is a valid alternate strategy, but it consumes additional space and involves extra steps. The simulation approach we are using is more space-efficient because it builds the result in-place, with minimal overhead. It is both cleaner and faster in practice.
Great observation! Now let’s take a moment to think about what kind of approach we’re actually following here.
We’re starting at one cell, and from there, we’re step-by-step navigating through the matrix — moving up-right or down-left based on the current direction, checking for boundaries, and adjusting our path accordingly.
We’re not building all diagonals ahead of time or using extra data structures — we’re just simulating the exact movement the way a person would trace it with their finger across the grid. That’s the essence of a simulation approach! We're not jumping around or pre-processing anything — we're literally walking the path, mimicking the traversal the problem describes, and collecting elements on the go.
Let's now see how our algorithm looks!
Diagonal Traverse Algorithm
- Initialize direction as upward. This will alternate after each diagonal.
- Start from the top-left corner of the matrix.
- If moving upward, go up-right along the diagonal while staying inside the matrix.
- If moving downward, go down-left along the diagonal while staying inside the matrix.
- If moving upward and go out of bounds, move to the next column if possible; otherwise, move to the next row.
- If moving downward and go out of bounds, move to the next row if possible; otherwise, move to the next column.
- After finishing a diagonal, switch the direction.
- Continue until all elements in the matrix are added to the result.
Approach
- Initialize Direction: Start with direction = up. We alternate between up-right and down-left after each diagonal.
- Set the Starting Point: Begin at the top-left of the matrix with row = 0, col = 0.
- Traverse the Diagonal
a. If the direction is up
→ Move up-right while within bounds using row--, col++
b. If the direction is down
→ Move down-left while within bounds using row++, col-- - Determine the Next Head (After Going Out of Bounds)
- If the direction was up and we go out of bounds
→ If col < n, then next head is row = row + 1, col = col
→ Else, next head is row = row + 1, col = n - 1 - If the direction was down and we go out of bounds
→ If row < m, then next head is row = row, col = col + 1
→ Else, next head is row = m - 1, col = col + 1
- Flip Direction: After each diagonal traversal, toggle the direction (up ⇄ down)
- End Condition: Continue until all elements from the matrix are added to the result array.
Dry-Run
Input: mat = [
[10, 20, 30, 40],
[50, 60, 70, 80],
[90, 100,110,120]]
Rows (m): 3
Columns (n): 4
Goal: Return all elements in diagonal order, following the zig-zag pattern.
Explanation:
We will track:
- row, col = current position
- direction = up or down
Start at (0, 0): → 10
Direction = up
- (0, 0) → 10 → Move up-right → out of bounds, switch to (0, 1)
Output so far: [10]
Direction: down - (0, 1) → 20
- (1, 0) → 50 → Move down-left → out of bounds, switch to (2, 0)
Output so far: [10, 20, 50]
Direction: up - (2, 0) → 90
- (1, 1) → 60
- (0, 2) → 30 → Move up-right → out of bounds, switch to (0, 3)
Output so far: [10, 20, 50, 90, 60, 30]
Direction: down - (0, 3) → 40
- (1, 2) → 70
- (2, 1) → 100 → Move down-left → out of bounds, switch to (2, 2)
Output so far: [10, 20, 50, 90, 60, 30, 40, 70, 100]
Direction: up - (2, 2) → 110
- (1, 3) → 80 → Move up-right → out of bounds, switch to (2, 3)
Output so far: [10, 20, 50, 90, 60, 30, 40, 70, 100, 110, 80]
Direction: down - (2, 3) → 120 → No more moves
Output so far: [10, 20, 50, 90, 60, 30, 40, 70, 100, 110, 80, 120]
Final Output: [10, 20, 50, 90, 60, 30, 40, 70, 100, 110, 80, 120]
Diagonal Traverse Solution
Now let's checkout the "Diagonal Traverse code" in C++, Java, Python and JavaScript.
"Diagonal Traverse" Code in all Languages.
1. Diagonal Traverse solution in C++ Try on Compiler
class Solution {
public:
vector<int> findDiagonalOrder(vector<vector<int>>& mat) {
// Check for empty matrix
if (mat.empty() || mat[0].empty()) return {};
// Get dimensions
int m = mat.size(), n = mat[0].size();
// Result array
vector<int> result;
result.reserve(m * n);
// Initialize position and direction
int row = 0, col = 0, direction = 1;
// Loop through matrix
while (row < m && col < n) {
// Add current value
result.push_back(mat[row][col]);
// Compute next position
int newRow = row + (direction == 1 ? -1 : 1);
int newCol = col + (direction == 1 ? 1 : -1);
// Check bounds
if (newRow < 0 || newRow == m || newCol < 0 || newCol == n) {
// Change direction
if (direction == 1) {
row += (col == n - 1 ? 1 : 0);
col += (col < n - 1 ? 1 : 0);
} else {
col += (row == m - 1 ? 1 : 0);
row += (row < m - 1 ? 1 : 0);
}
direction = 1 - direction;
} else {
row = newRow;
col = newCol;
}
}
return result;
}
};2. Diagonal Traverse Solution in Java Try on Compiler
class Solution {
public static int[] findDiagonalOrder(int[][] matrix) {
// Check for empty matrix
if (matrix == null || matrix.length == 0) {
return new int[0];
}
// Get the dimensions of the matrix
int N = matrix.length;
int M = matrix[0].length;
// Initialize position and direction
int row = 0, col = 0;
int direction = 1;
// Array to hold the result
int[] result = new int[N * M];
int index = 0;
// Loop through each element
while (row < N && col < M) {
// Place current element in result
result[index++] = matrix[row][col];
// Calculate next position
int newRow = row + (direction == 1 ? -1 : 1);
int newCol = col + (direction == 1 ? 1 : -1);
// Check boundaries
if (newRow < 0 || newRow == N || newCol < 0 || newCol == M) {
// If moving upwards
if (direction == 1) {
// Move right if possible, else move down
row += (col == M - 1 ? 1 : 0);
col += (col < M - 1 ? 1 : 0);
} else {
// Move down if possible, else move right
col += (row == N - 1 ? 1 : 0);
row += (row < N - 1 ? 1 : 0);
}
// Flip direction
direction = 1 - direction;
} else {
// Continue in current direction
row = newRow;
col = newCol;
}
}
return result;
}
}3. Diagonal Traverse Solution in Python Try on Compiler
class Solution:
def findDiagonalOrder(self, mat: List[List[int]]) -> List[int]:
# Handle empty input
if not mat or not mat[0]:
return []
# Get matrix dimensions
m, n = len(mat), len(mat[0])
# Initialize pointers
row, col, direction = 0, 0, 1
# Output array
result = []
# Traverse the matrix
while row < m and col < n:
# Append current value
result.append(mat[row][col])
# Compute next position
new_row = row + (-1 if direction == 1 else 1)
new_col = col + (1 if direction == 1 else -1)
# Check bounds
if new_row < 0 or new_row == m or new_col < 0 or new_col == n:
if direction == 1:
# Move right or down
row += (col == n - 1)
col += (col < n - 1)
else:
# Move down or right
col += (row == m - 1)
row += (row < m - 1)
# Flip direction
direction = 1 - direction
else:
row, col = new_row, new_col
return result
4. Diagonal Traverse solution in JavaScript Try on Compiler
/**
* @param {number[][]} mat
* @return {number[]}
*/
var findDiagonalOrder = function(mat) {
// Handle empty matrix
if (mat.length === 0 || mat[0].length === 0) return [];
// Get dimensions
const m = mat.length, n = mat[0].length;
// Result array
const result = [];
// Start positions and direction
let row = 0, col = 0, direction = 1;
// Traverse all elements
while (row < m && col < n) {
// Push current value
result.push(mat[row][col]);
// Calculate next cell
let newRow = row + (direction === 1 ? -1 : 1);
let newCol = col + (direction === 1 ? 1 : -1);
// Check bounds
if (newRow < 0 || newRow === m || newCol < 0 || newCol === n) {
if (direction === 1) {
// Move right or down
row += (col === n - 1 ? 1 : 0);
col += (col < n - 1 ? 1 : 0);
} else {
// Move down or right
col += (row === m - 1 ? 1 : 0);
row += (row < m - 1 ? 1 : 0);
}
direction = 1 - direction;
} else {
row = newRow;
col = newCol;
}
}
return result;
};
Diagonal Traverse Complexity Analysis
Time Complexity: O(m x n)
The Diagonal Traverse algorithm processes each element of the matrix exactly once.
- Traversing each element:
→ Each cell is visited once in a zig-zag diagonal fashion.
→ This gives a time complexity of O(m × n),
where m is the number of rows and n is the number of columns. - Direction switch and index updates:
→ All direction changes and index updates happen in constant time and do not add to complexity.
Total Time Complexity: O(m × n)
Space Complexity: O(m × n)
Auxiliary Space Complexity: Auxiliary space refers to the extra space required by the algorithm other than extra space.
- Result array:
We store all elements of the matrix in the result, which takes O(m × n) space. - Other variables:
We use a few integers for tracking position and direction → O(1)
Auxiliary Space Complexity:
O(m × n) for the result array + O(1) for variables = O(m × n) total.
Total Space Complexity:
- Input matrix: O(m × n) (already given)
- Result array (output): O(m × n)
- Constant space for pointers: O(1)
Total Space Complexity: O(m × n)
Similar Problems
Given an m x n matrix, return all elements of the matrix in spiral order.
Given an m x n integer matrix matrix, if an element is 0, set its entire row and column to 0's.