Log inSign up
mediumLeetCodeNot Started

Diagonal Traverse

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Arrays
Solve on LeetCode
Lesson

Problem Statement

Given an m x n matrix mat, return an array of all the elements of the array in a diagonal order.

The traversal starts at mat[0][0] moving diagonally upwards to the right, then turns downwards to the left along the next diagonal, alternating direction on each successive diagonal.

Example 1 · Standard 3x3 Matrix:

Input: mat = [[1,2,3],[4,5,6],[7,8,9]]
Output: [1,2,4,7,5,3,6,8,9]
Explanation: The diagonals are: - d = 0: [1] (upward) - d = 1: [2, 4] (downward -> 2, 4) - d = 2: [7, 5, 3] (upward -> 7, 5, 3) - d = 3: [6, 8] (downward -> 6, 8) - d = 4: [9] (upward -> 9) Result: [1, 2, 4, 7, 5, 3, 6, 8, 9].

Example 2 · 2x2 Matrix:

Input: mat = [[1,2],[3,4]]
Output: [1,2,3,4]
Explanation: Diagonal traversal yields [1, 2, 3, 4].

Constraints:

  • m == mat.length
  • n == mat[i].length
  • 1 <= m, n <= 104
  • 1 <= m * n <= 104
  • -105 <= mat[i][j] <= 105

Prerequisites

Before attempting this problem, you should be comfortable with:

  • 2D matrix indexing and boundary conditions
  • Understanding the anti-diagonal coordinate invariant r + c = constant

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Master the diagonal invariant r + c = constant on 2D grids.
  • Formulate closed-form boundary starting positions for upward and downward diagonals.
  • Eliminate dynamic list allocations in matrix traversals.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Input structure involves an array or contiguous sequence with constraints on element relationships.
  • Optimal solution requires avoiding O(N2) exhaustive searches through state tracking or pointers.
  • Subproblem exhibits optimal substructure or monotonicity enabling linear or logarithmic processing.

Algorithmic Decision Tree:

  • If the array is sorted or can be sorted without violating problem requirements, evaluate Two Pointers or Binary Search.
  • If tracking contiguous subsegments with monotone expansion/shrinkage, apply Sliding Window.
  • If frequency or complement lookups are required in O(1) time, use a Hash Map or Frequency Array.

Connected Patterns:

Spiral MatrixRotate ImageToeplitz Matrix

1. Group by Anti-Diagonal Index (Brute Force)

Intuition

In an m x n matrix, all cells with the same sum r + c lie on the same anti-diagonal. Group cells by r + c into m + n - 1 buckets. Reverse even-numbered buckets (or odd, depending on starting direction) and flatten into a 1D result list.

When to apply: Use to understand the diagonal invariant r + c == constant.

Bucket by (r + c) Trace

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [1, 2, 3, 4, 5, 6, 7, 8, 9]
Current operationSTEP 1 OF 6
Matrix: [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
Visual state
Values and pointers at this exact step
matrix
c0
c1
c2
r0
1
↑ sum 0
2
3
r1
4
5
6
r2
7
8
9
Variables at this step
buckets
5
Check / comparison
Diagonal sums: 0, 1, 2, 3, 4.
Decision / next transition
Initialize 5 diagonal buckets.
Why this step matters

Matrix: [[1, 2, 3], [4, 5, 6], [7, 8, 9]]. Sums range from 0 to 4 (m + n - 2).

Step 1 / 6
JAVA SOLUTIONCLEAN & OPTIMIZED
1import java.util.*;
2
3public class Main {
4 public static class Solution {
5 public int[] findDiagonalOrder(int[][] mat) {
6 if (mat == null || mat.length == 0) return new int[0];
7 int m = mat.length, n = mat[0].length;
8 List<List<Integer>> buckets = new ArrayList<>();
9 for (int i = 0; i < m + n - 1; i++) buckets.add(new ArrayList<>());
10
11 for (int r = 0; r < m; r++) {
12 for (int c = 0; c < n; c++) {
13 buckets.get(r + c).add(mat[r][c]);
14 }
15 }
16
17 int[] res = new int[m * n];
18 int idx = 0;
19 for (int i = 0; i < buckets.size(); i++) {
20 List<Integer> b = buckets.get(i);
21 if (i % 2 == 0) {
22 for (int j = b.size() - 1; j >= 0; j--) res[idx++] = b.get(j);
23 } else {
24 for (int j = 0; j < b.size(); j++) res[idx++] = b.get(j);
25 }
26 }
27 return res;
28 }
29 }
30
31 public static void main(String[] args) {
32 Solution sol = new Solution();
33 int[][] mat = {
34 {1, 2, 3},
35 {4, 5, 6},
36 {7, 8, 9}
37 };
38 System.out.println("Diagonal order: " + Arrays.toString(sol.findDiagonalOrder(mat)));
39 }
40}

Time & Space Complexity

  • Time complexity: O(m * n) — All m*n cells are visited and added to buckets.
  • Space complexity: O(m * n) — Buckets store all m*n elements.

Why Brute Force Doesn't Scale:

For a 10,000-element matrix, dynamic lists cause thousands of heap reallocations.

Direct diagonal calculation writes directly into a pre-allocated array of size M*N in 0 extra heap memory.

2. Boundary Bounce Simulation

Intuition

Maintain current row r and column c with a direction boolean up. When moving up-right: if c == n - 1, step down (r++) and flip direction; else if r == 0, step right (c++) and flip direction; else r--, c++. Similar logic applies when moving down-left.

When to apply: Use to understand state transitions at corners and edges.

Direction Bounce Simulation Trace

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [1, 2, 3, 4, 5, 6, 7, 8, 9]
Current operationSTEP 1 OF 6
Start at (0,0)=1 with up=true
Visual state
Values and pointers at this exact step
matrix
c0
c1
c2
r0
1
↑ r=0,c=0
2
3
r1
4
5
6
r2
7
8
9
Variables at this step
r
0
c
1
up
false
res
[1]
Check / comparison
At top edge r=0.
Decision / next transition
Bounce: move right to c=1, flip up=false.
Why this step matters

Start at (0,0)=1 with up=true. Add 1.

Step 1 / 6
JAVA SOLUTIONCLEAN & OPTIMIZED
1import java.util.*;
2
3public class Main {
4 public static class Solution {
5 public int[] findDiagonalOrder(int[][] mat) {
6 if (mat == null || mat.length == 0) return new int[0];
7 int m = mat.length, n = mat[0].length;
8 int[] res = new int[m * n];
9 int r = 0, c = 0;
10
11 for (int i = 0; i < m * n; i++) {
12 res[i] = mat[r][c];
13 if ((r + c) % 2 == 0) { // moving up-right
14 if (c == n - 1) { r++; }
15 else if (r == 0) { c++; }
16 else { r--; c++; }
17 } else { // moving down-left
18 if (r == m - 1) { c++; }
19 else if (c == 0) { r++; }
20 else { r++; c--; }
21 }
22 }
23 return res;
24 }
25 }
26
27 public static void main(String[] args) {
28 Solution sol = new Solution();
29 int[][] mat = {
30 {1, 2, 3},
31 {4, 5, 6},
32 {7, 8, 9}
33 };
34 System.out.println("Diagonal order: " + Arrays.toString(sol.findDiagonalOrder(mat)));
35 }
36}

Time & Space Complexity

  • Time complexity: O(m * n) — Single linear pass filling the m*n result array.
  • Space complexity: O(1) auxiliary — O(1) memory outside output array.

3. Direct Diagonal Sweep with Head Calculation (Optimal & Standard)

Intuition

For each diagonal d from 0 to m + n - 2: If d is even (up-right), the head starts at row = min(d, m - 1), col = d - row; decrement row and increment col. If d is odd (down-left), the head starts at col = min(d, n - 1), row = d - col; decrement col and increment row.

When to apply: Use as the cleanest and most mathematically sound optimal approach.

Direct Diagonal Head Sweep Trace

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [1, 2, 3, 4, 5, 6, 7, 8, 9]
Current operationSTEP 1 OF 6
d=0 (even, up-right): Head at r=0, c=0
Visual state
Values and pointers at this exact step
matrix
c0
c1
c2
r0
1
↑ d=0
2
3
r1
4
5
6
r2
7
8
9
Variables at this step
d
0
head
(0,0)
res
[1]
Check / comparison
d=0 sweep.
Decision / next transition
Add 1 to result.
Why this step matters

d=0 (even, up-right): Head at r=0, c=0. Value = 1.

Step 1 / 6
JAVA SOLUTIONCLEAN & OPTIMIZED
1import java.util.*;
2
3public class Main {
4 public static class Solution {
5 public int[] findDiagonalOrder(int[][] mat) {
6 if (mat == null || mat.length == 0) return new int[0];
7 int m = mat.length, n = mat[0].length;
8 int[] res = new int[m * n];
9 int idx = 0;
10
11 for (int d = 0; d < m + n - 1; d++) {
12 if (d % 2 == 0) {
13 int r = Math.min(d, m - 1);
14 int c = d - r;
15 while (r >= 0 && c < n) {
16 res[idx++] = mat[r][c];
17 r--;
18 c++;
19 }
20 } else {
21 int c = Math.min(d, n - 1);
22 int r = d - c;
23 while (c >= 0 && r < m) {
24 res[idx++] = mat[r][c];
25 r++;
26 c--;
27 }
28 }
29 }
30 return res;
31 }
32 }
33
34 public static void main(String[] args) {
35 Solution sol = new Solution();
36 int[][] mat = {
37 {1, 2, 3},
38 {4, 5, 6},
39 {7, 8, 9}
40 };
41 System.out.println("Diagonal order: " + Arrays.toString(sol.findDiagonalOrder(mat)));
42 }
43}

Time & Space Complexity

  • Time complexity: O(m * n) — Every element is visited exactly once in order.
  • Space complexity: O(1) auxiliary — O(1) extra space outside the returned array.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Brute Force — Hash Map Grouping by (r + c)O(M * N)O(M * N)Collect all elements into buckets indexed by r + c. Then reverse the odd-indexed bucket lists and concatenate.Auxiliary list allocations.
2.Better — Coordinate Step Simulation with Edge BouncingO(M * N)O(1)Simulate a pointer (r, c) with direction dir = +1 (up-right) or -1 (down-left). When hitting matrix boundaries, clamp coordinates and flip direction.Multiple nested boundary condition branches.
3.Optimal — Direct Diagonal Bounds CalculationOptimalO(M * N)O(1)Iterate diagonal index d from 0 to m + n - 2. Compute start coordinate (r, c) based on d, then step until reaching opposite boundary.None; theoretical optimum.

Common Pitfalls & Crucial Edge Cases

Off-by-One Errors

Incorrect boundary indexing when adjusting pointers or array slices.

Integer Overflow

Using 32-bit signed integer types when accumulative operations exceed 231 - 1 in C++/Java.

Unnecessary Memory Allocation

Allocating large auxiliary arrays or objects inside inner loops causing GC overhead.

Failing to Reset Loop State

Not re-initializing state variables or counters between iterations or subproblems.

Crucial Edge Cases to Validate:

  • Empty or Single Element Array — Handle minimal input sizes (N = 0 or N = 1) cleanly without out-of-bounds errors.
  • Duplicate Elements — Verify behavior when all elements are identical (e.g. all 0s or all equal values).
  • Extreme Numerical Values — Account for maximum/minimum allowed constraint values (-109 to 109) to prevent overflow.
  • Boundary Conditions — Ensure correct execution when target or match is located at the first or last index.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Always state the brute force baseline before presenting the optimal solution to demonstrate structured problem solving.
  2. Explicitly verify boundary conditions (empty arrays, single elements, duplicates, extremes) out loud with the interviewer.
  3. Analyze both time and auxiliary space complexities clearly, explaining trade-offs between speed and memory allocation.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.What is the optimal time and auxiliary space complexity for Diagonal Traverse?

2.Why is the brute force approach suboptimal for large inputs in Diagonal Traverse?

3.Which data structure or technique enables the optimal solution for Diagonal Traverse?

Back to DSA Sheet