#498

Medium

LeetCode Problem Workspace

Diagonal Traverse

Traverse a matrix diagonally and return all elements in the specific zig-zag order required by the problem pattern.

Problem Statement

Given an m x n matrix mat, return a single array containing all elements in a diagonal zig-zag order. Traverse each diagonal starting from the top-left element and alternate directions between moving up-right and down-left for each successive diagonal.

For example, with mat = [[1,2,3],[4,5,6],[7,8,9]], the traversal order is [1,2,4,7,5,3,6,8,9]. Ensure your solution handles any matrix size within the constraints and correctly switches directions on each diagonal.

Examples

Example 1

Input: mat = [[1,2,3],[4,5,6],[7,8,9]]

Output: [1,2,4,7,5,3,6,8,9]

Example details omitted.

Example 2

Input: mat = [[1,2],[3,4]]

Output: [1,2,3,4]

Example details omitted.

Constraints

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

Solution Approach

Iterate Diagonals Using Index Sums

Loop through all possible sums of row and column indices. For each sum, collect elements that satisfy i+j=sum. Reverse the order on alternating diagonals to match the zig-zag pattern.

Use Direction Flag

Maintain a boolean flag to indicate current direction. If moving up-right, traverse elements in reverse order within the current diagonal; if moving down-left, traverse normally. Toggle the flag after completing each diagonal.

Boundary Checks and Result Array

Ensure all indices are valid within matrix bounds to avoid out-of-range errors. Append each element to a pre-allocated result array of size m*n for optimal space usage, adhering to the array plus matrix pattern.

Complexity Analysis

Metric	Value
Time	O(N \cdot M)
Space	O(1)

Time complexity is O(M*N) as each element is visited exactly once. Space complexity is O(1) extra if output array is not counted; using only loop variables and flags.

What Interviewers Usually Probe

Candidate starts by recognizing the diagonal index sum pattern.
Candidate correctly alternates traversal direction per diagonal.
Candidate efficiently handles matrix boundaries without errors.

Common Pitfalls or Variants

Common pitfalls

Incorrectly reversing elements on diagonals leading to wrong order.
Off-by-one errors when accessing the last row or column.
Using extra space unnecessarily instead of in-place collection into the result array.

Follow-up variants

Traverse diagonals starting from bottom-right instead of top-left.
Return only the elements of even-numbered diagonals.
Perform the traversal but output each diagonal as a separate subarray instead of flattening.

FAQ

What is the main pattern behind Diagonal Traverse?

The main pattern is summing row and column indices to identify diagonals and alternating the traversal direction for each diagonal.

Can Diagonal Traverse handle non-square matrices?

Yes, the solution correctly handles any m x n matrix within the given constraints using the same diagonal summing logic.

Why do some diagonals need to be reversed?

Reversing every other diagonal ensures the zig-zag order is maintained, matching the problem's required output sequence.

What is the time complexity of Diagonal Traverse?

Each element is visited once, so the time complexity is O(M*N), where M and N are matrix dimensions.

How does the array plus matrix pattern apply here?

Each diagonal is treated as an array derived from matrix indices; collecting elements efficiently into a single output array follows the pattern precisely.

terminal

Solution

Solution 1: 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$.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

class Solution:
    def findDiagonalOrder(self, mat: List[List[int]]) -> List[int]:
        m, n = len(mat), len(mat[0])
        ans = []
        for k in range(m + n - 1):
            t = []
            i = 0 if k < n else k - n + 1
            j = k if k < n else n - 1
            while i < m and j >= 0:
                t.append(mat[i][j])
                i += 1
                j -= 1
            if k % 2 == 0:
                t = t[::-1]
            ans.extend(t)
        return ans

Continue Practicing

#566 reshape the matrix #289 game of life #749 contain virus