Diagonal Traverse solution and explanation
Cisco
Google
9 more videos on this problem
Diagonal Traverse | Live Coding with Explanation | Leetcode - 498Algorithms Made Easy · 6:56 · 59K views
DIAGONAL TRAVERSE | LEETCODE # 498 | PYTHON SOLUTIONCracking FAANG · 12:57 · 26K views
Diagonal Traverse | Leetcode 498 | Similar to Leetcode 1329 | codestorywithMIKcodestorywithMIK · 13:04 · 24K views
[Java] Leetcode 498. Diagonal Traverse [Array #2]Eric Programming · 9:42 · 3K views
498. Diagonal Traverse - English VersionSimple Code - 단순코드 · 12:18 · 2K views
Diagonal Traverse - LeetCode 498 - JavaScriptAlgoJS · 6:13 · 1K views
Leetcode 498 Diagonal TraverseRen Zhang · 11:23 · 1K views
498. Diagonal Traverse | Leetcode Daily - PythonLeetcode Daily · 5:51 · 1K views
Leetcode 498. Diagonal Traverse | Matrix Traversal Patterns | Python SolutionStatLearn Tech · 15:14 · 1K views
LeetCode 498: Diagonal Traverse | Java Solution | Matrix TraversalCode Scribbler · 5:32 · 838 views
The problem
Given an m x n matrix mat, return an array of all the elements of the array in a diagonal order.
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]
Constraints:
m == mat.lengthn == mat[i].length1 <= m, n <= 1041 <= m * n <= 104-105 <= mat[i][j] <= 105
Approach overview
Problem Overview: Given an matrix with m x n elements, return all values in diagonal order. The traversal alternates direction for each diagonal: one goes upward-right, the next downward-left, producing a zigzag pattern across the matrix.
Approach 1: Direct Simulation (Time: O(m*n), Space: O(1))
This method simulates the traversal exactly as described. Start from the top-left cell and maintain a direction flag: either moving up-right or down-left. On each step, update the row and column based on the current direction. When you hit a boundary (top row, bottom row, left column, or right column), change direction and adjust the position to the next valid starting point of the following diagonal.
The key insight is that every matrix element belongs to exactly one diagonal step in the traversal. Boundary handling drives the algorithm: if moving up-right and you reach the top edge, shift right and flip direction; if you reach the right edge, move down and flip direction. Similar logic applies when moving down-left. Because each cell is visited once, the runtime is O(m*n) with O(1) auxiliary space besides the output array. This approach works well when you want constant extra memory and clear control over traversal order.
Approach 2: Hash Map of Diagonals (Time: O(m*n), Space: O(m+n))
Every diagonal in a matrix shares the same value of row + col. Iterate through the matrix and group elements using this key in a hash map or list array indexed by row + col. Each key represents one diagonal. After grouping, process the diagonals in order from 0 to m+n-2.
The zigzag requirement comes from reversing elements on alternating diagonals. For even-indexed diagonals, reverse the collected list before appending to the result. For odd ones, keep the order as-is. This technique separates traversal from ordering logic, which simplifies implementation and avoids complex boundary checks.
The algorithm scans the matrix once (O(m*n)) and stores diagonals in a structure with at most m+n-1 groups, resulting in O(m+n) extra space. It relies heavily on concepts from arrays and hash maps to organize elements efficiently.
Recommended for interviews: Direct Simulation is typically what interviewers expect because it demonstrates control over matrix traversal and boundary conditions. The hash map approach is easier to reason about and implement quickly, but it uses additional memory. Showing the simulation first proves you understand how diagonals move through a matrix, while mentioning the grouping trick highlights algorithmic flexibility.
Approach 1: Approach 1: Direct Simulation
This approach involves a direct simulation of the diagonal traversal. We use two variables, i and j, to represent the current position in the matrix, and a boolean direction to indicate whether we are moving upwards or downwards diagonally. The process toggles the direction once the boundaries of the matrix are reached, ensuring that the entire matrix is traversed correctly in a zig-zag order.
from typing import List
def findDiagonalOrder(mat: List[List[int]]) -> List[int]:
if not mat: return []
m, n = len(mat), len(mat[0])
result, i, j, direction = [], 0, 0, 1
while len(result) < m * n:
result.append(mat[i][j])
if direction == 1: # Moving up
if j == n - 1: i, direction = i + 1, -1
elif i == 0: j, direction = j + 1, -1
else: i, j = i - 1, j + 1
else: # Moving down
if i == m - 1: j, direction = j + 1, 1
elif j == 0: i, direction = i + 1, 1
else: i, j = i + 1, j - 1
return resultimport java.util.ArrayList;
import java.util.List;
class Solution {
public int[] findDiagonalOrder(int[][] mat) {
if (mat.length == 0) return new int[0];
int m = mat.length, n = mat[0].length;
int[] result = new int[m * n];
int idx = 0, i = 0, j = 0;
int direction = 1;
while (idx < m * n) {
result[idx++] = mat[i][j];
if (direction == 1) { // Moving up
if (j == n - 1) { i++; direction = -1; }
else if (i == 0) { j++; direction = -1; }
else { i--; j++; }
} else { // Moving down
if (i == m - 1) { j++; direction = 1; }
else if (j == 0) { i++; direction = 1; }
else { i++; j--; }
}
}
return result;
}
}#include <vector>
using namespace std;
vector<int> findDiagonalOrder(vector<vector<int>>& mat) {
if (mat.empty()) return {};
int m = mat.size(), n = mat[0].size();
vector<int> result;
result.reserve(m * n);
int i = 0, j = 0, direction = 1;
while (result.size() < m * n) {
result.push_back(mat[i][j]);
if (direction == 1) { // Moving up
if (j == n - 1) { i++; direction = -1; }
else if (i == 0) { j++; direction = -1; }
else { i--; j++; }
} else { // Moving down
if (i == m - 1) { j++; direction = 1; }
else if (j == 0) { i++; direction = 1; }
else { i++; j--; }
}
}
return result;
}var findDiagonalOrder = function(mat) {
if (mat.length === 0) return [];
let m = mat.length, n = mat[0].length;
let result = [], i = 0, j = 0, direction = 1;
while (result.length < m * n) {
result.push(mat[i][j]);
if (direction === 1) { // Moving up
if (j === n - 1) { i++; direction = -1; }
else if (i === 0) { j++; direction = -1; }
else { i--; j++; }
} else { // Moving down
if (i === m - 1) { j++; direction = 1; }
else if (j === 0) { i++; direction = 1; }
else { i++; j--; }
}
}
return result;
};#include <stdio.h>
#include <stdlib.h>
int* findDiagonalOrder(int** mat, int matSize, int* matColSize, int* returnSize) {
if (matSize == 0) {
*returnSize = 0;
return NULL;
}
int m = matSize, n = matColSize[0];
*returnSize = m * n;
int* result = (int*)malloc((*returnSize) * sizeof(int));
int idx = 0;
int i = 0, j = 0, direction = 1;
while (idx < *returnSize) {
result[idx++] = mat[i][j];
if (direction == 1) { // Moving up
if (j == n - 1) { i++; direction = -1; }
else if (i == 0) { j++; direction = -1; }
else { i--; j++; }
} else { // Moving down
if (i == m - 1) { j++; direction = 1; }
else if (j == 0) { i++; direction = 1; }
else { i++; j--; }
}
}
return result;
}public class Solution {
public int[] FindDiagonalOrder(int[][] mat) {
if (mat.Length == 0) return new int[0];
int m = mat.Length, n = mat[0].Length;
int[] result = new int[m * n];
int idx = 0, i = 0, j = 0, direction = 1;
while (idx < m * n) {
result[idx++] = mat[i][j];
if (direction == 1) { // Moving up
if (j == n - 1) { i++; direction = -1; }
else if (i == 0) { j++; direction = -1; }
else { i--; j++; }
} else { // Moving down
if (i == m - 1) { j++; direction = 1; }
else if (j == 0) { i++; direction = 1; }
else { i++; j--; }
}
}
return result;
}
}This Python solution tracks indices i and j while adjusting direction at matrix boundaries. result list collects elements in diagonal order, switching direction using a direction flag.
Time Complexity: O(m * n), ensuring each element is visited.
Space Complexity: O(m * n) for storing the final result.
Approach 2: Approach 2: Hash Map of Diagonals
This approach leverages a hash map (or dictionary) to collect elements that belong to the same diagonal. The sum of the row and column indices i + j serves as the key, grouping all elements located on the same diagonal. After populating the hash map, we extract and append these elements to the result array, reversing them as needed to maintain the diagonal order.
from typing import List
from collections import defaultdict
def findDiagonalOrder(mat: List[List[int]]) -> List[int]:
diagonals = defaultdict(list)
m, n = len(mat), len(mat[0])
for i in range(m):
for j in range(n):
diagonals[i + j].append(mat[i][j])
result = []
for key in range(m + n - 1):
if key % 2 == 0:
result.extend(reversed(diagonals[key]))
else:
result.extend(diagonals[key])
return resultimport java.util.*;
class Solution {
public int[] findDiagonalOrder(int[][] mat) {
int m = mat.length, n = mat[0].length;
Map<Integer, List<Integer>> diagonals = new HashMap<>();
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
diagonals.computeIfAbsent(i + j, k -> new ArrayList<>()).add(mat[i][j]);
}
}
List<Integer> result = new ArrayList<>();
for (int k = 0; k < m + n - 1; k++) {
List<Integer> diag = diagonals.get(k);
if (k % 2 == 0) Collections.reverse(diag);
result.addAll(diag);
}
return result.stream().mapToInt(Integer::intValue).toArray();
}
}#include <vector>
#include <unordered_map>
using namespace std;
vector<int> findDiagonalOrder(vector<vector<int>>& mat) {
int m = mat.size(), n = mat[0].size();
unordered_map<int, vector<int>> diagonals;
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
diagonals[i + j].push_back(mat[i][j]);
}
}
vector<int> result;
for (int k = 0; k < m + n - 1; ++k) {
if (k % 2 == 0) {
reverse(diagonals[k].begin(), diagonals[k].end());
}
result.insert(result.end(), diagonals[k].begin(), diagonals[k].end());
}
return result;
}var findDiagonalOrder = function(mat) {
let m = mat.length, n = mat[0].length;
let diagonals = new Map();
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
if (!diagonals.has(i + j)) diagonals.set(i + j, []);
diagonals.get(i + j).push(mat[i][j]);
}
}
let result = [];
for (let k = 0; k < m + n - 1; k++) {
let diag = diagonals.get(k);
if (k % 2 === 0) diag.reverse();
result.push(...diag);
}
return result;
};#include <stdio.h>
#include <stdlib.h>
int* findDiagonalOrder(int** mat, int matSize, int* matColSize, int* returnSize) {
int m = matSize, n = matColSize[0];
*returnSize = m * n;
int **map = (int **)malloc((m + n - 1) * sizeof(int *));
int *sizes = (int *)calloc(m + n - 1, sizeof(int));
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
int sum = i + j;
if (!map[sum]) map[sum] = (int *)malloc((m > n ? m : n) * sizeof(int));
map[sum][sizes[sum]++] = mat[i][j];
}
}
int *result = (int *)malloc((*returnSize) * sizeof(int));
int idx = 0;
for (int k = 0; k < m + n - 1; ++k) {
if (k % 2 == 0) {
for (int s = sizes[k] - 1; s >= 0; --s) {
result[idx++] = map[k][s];
}
} else {
for (int s = 0; s < sizes[k]; ++s) {
result[idx++] = map[k][s];
}
}
free(map[k]);
}
free(map);
free(sizes);
return result;
}using System;
using System.Collections.Generic;
public class Solution {
public int[] FindDiagonalOrder(int[][] mat) {
int m = mat.Length, n = mat[0].Length;
Dictionary<int, List<int>> diagonals = new Dictionary<int, List<int>>();
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (!diagonals.ContainsKey(i + j)) diagonals[i + j] = new List<int>();
diagonals[i + j].Add(mat[i][j]);
}
}
List<int> result = new List<int>();
for (int k = 0; k < m + n - 1; k++) {
if (k % 2 == 0) diagonals[k].Reverse();
result.AddRange(diagonals[k]);
}
return result.ToArray();
}
}Python uses defaultdict to manage lists of diagonal elements. The i + j sum serves as the key, organizing elements for later collection into a single output result list based on zig-zag criteria.
Time Complexity: O(m * n), every element is accessed once.
Space Complexity: O(m * n), for maintaining lists of diagonals before flattening.
Approach 3: Fixed Point Traversal
For each round k, we fix the starting point from the top-right and traverse diagonally to the bottom-left to get t. If k is even, we reverse t.
The time complexity is O(m times n), and the space complexity is O(1). Ignoring the space used for the answer.
function findDiagonalOrder(mat: number[][]): number[] {
const m = mat.length;
const n = mat[0].length;
const ans: number[] = [];
for (let k = 0; k < m + n - 1; k++) {
const t: number[] = [];
let i = k < n ? 0 : k - n + 1;
let j = k < n ? k : n - 1;
while (i < m && j >= 0) {
t.push(mat[i][j]);
i++;
j--;
}
if (k % 2 === 0) {
t.reverse();
}
ans.push(...t);
}
return ans;
}func findDiagonalOrder(mat [][]int) []int {
m := len(mat)
n := len(mat[0])
ans := make([]int, 0, m*n)
for k := 0; k < m+n-1; k++ {
t := make([]int, 0)
var i, j int
if k < n {
i = 0
j = k
} else {
i = k - n + 1
j = n - 1
}
for i < m && j >= 0 {
t = append(t, mat[i][j])
i++
j--
}
if k%2 == 0 {
slices.Reverse(t)
}
ans = append(ans, t...)
}
return ans
}impl Solution {
pub fn find_diagonal_order(mat: Vec<Vec<i32>>) -> Vec<i32> {
let m = mat.len();
let n = mat[0].len();
let mut ans = Vec::with_capacity(m * n);
for k in 0..(m + n - 1) {
let mut t = Vec::new();
let (mut i, mut j) = if k < n {
(0, k)
} else {
(k - n + 1, n - 1)
};
while i < m && j < n {
t.push(mat[i][j]);
i += 1;
if j == 0 { break; }
j -= 1;
}
if k % 2 == 0 {
t.reverse();
}
ans.extend(t);
}
ans
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Approach 1: Direct Simulation | Time Complexity: O(m * n), ensuring each element is visited. |
| Approach 2: Hash Map of Diagonals | Time Complexity: O(m * n), every element is accessed once. |
| Fixed Point Traversal | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Direct Simulation | O(m*n) | O(1) | Preferred in interviews when you need constant extra memory and precise traversal control |
| Hash Map of Diagonals | O(m*n) | O(m+n) | Cleaner implementation when grouping elements by diagonal index is easier than handling boundaries |
Frequently asked questions
Is Diagonal Traverse easy or hard?
Diagonal Traverse is considered a medium-level problem. The main challenge comes from correctly handling edge cases when the traversal hits matrix borders and ensuring the direction switches at the right time.
How to solve Diagonal Traverse in O(n)?
The optimal solution runs in O(m*n) because all matrix elements must be processed. Use a simulation approach that moves diagonally and flips direction when hitting matrix boundaries. Another method groups elements by the key row+col and then processes diagonals with alternating order.
What is the best approach for Diagonal Traverse?
Direct simulation is the most common approach. It tracks the current direction (up-right or down-left) and switches direction whenever a matrix boundary is reached. The algorithm visits each element once, giving O(m*n) time and O(1) extra space, which makes it efficient and interview-friendly.
What data structure is used in Diagonal Traverse?
The simulation approach mainly uses arrays and index variables. The alternative grouping method uses a hash map or array of lists keyed by row+col to store elements belonging to the same diagonal before constructing the final traversal order.
What is the time complexity of Diagonal Traverse?
The time complexity is O(m*n) where m is the number of rows and n is the number of columns. Every matrix element is visited exactly once during the traversal. Space complexity is O(1) for the simulation method or O(m+n) if diagonals are stored in a hash map.
Diagonal Traverse Python or Java solution approach?
Both Python and Java implementations typically follow the direct simulation pattern. Maintain row, column, and direction variables, append elements to the result, and adjust direction when hitting matrix edges. The algorithm remains O(m*n) with constant extra space.
Is Diagonal Traverse asked at Google, Amazon, or Meta?
Matrix traversal problems like Diagonal Traverse frequently appear in interviews at companies such as Amazon, Google, and Meta. They test boundary handling, index manipulation, and understanding of matrix patterns rather than advanced data structures.