Limited Time Offer:Up to 25% off Hello Interview Premium

⌘K

Tutor

Get Premium

Leetcode 498. Diagonal Traverse

Return the elements of an m×n matrix in diagonal (zigzag) order, alternating between up-right and down-left along each diagonal. The core insight is to group cells by their i+j diagonal index and reverse every other group to produce the alternating traversal while handling boundary lengths.

Asked at:

Meta

DESCRIPTION

Input:

matrix = [[1,2,3],[4,5,6],[7,8,9]]

Output:

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

Explanation: Traverse diagonals in zigzag order: (1) → (2,4) → (7,5,3) → (6,8) → (9). Even diagonals go one direction, odd diagonals go the opposite direction.

Constraints:

m == matrix.length
n == matrix[i].length
1 <= m, n <= 10^4
1 <= m * n <= 10^4
-10^5 <= matrix[i][j] <= 10^5

Understanding the Problem

Let's understand what we're being asked to do. We have a matrix (2D array) like:

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

We need to return elements in diagonal zigzag order: [1, 2, 4, 7, 5, 3, 6, 8, 9].

Notice the pattern: we traverse diagonals alternately. First diagonal goes down-left (1), second goes up-right (2, 4), third goes down-left (7, 5, 3), fourth goes up-right (6, 8), fifth goes down-left (9).

Key observation: Elements on the same diagonal share the property that their row index + column index equals the same value. For example, (0,2), (1,1), (2,0) all have i+j=2.

Edge cases to consider: What if the matrix is 1×n (single row)? What if it's m×1 (single column)? What if it's empty? How do we handle the alternating direction for each diagonal?

Brute Force Approach

The straightforward approach is to simulate the zigzag movement directly: start at (0,0) and follow movement rules (move up-right when going up diagonals, move down-left when going down diagonals, handle boundary conditions to switch directions). Track the current direction and position, updating them based on whether we hit a boundary (top/bottom/left/right edge). This approach requires careful handling of multiple edge cases and direction changes, making it error-prone and harder to understand.

Visualization

def diagonal_order(matrix):
    """
    Return elements of m×n matrix in diagonal zigzag order.
    Brute force: simulate zigzag movement with direction tracking.
    """
    if not matrix or not matrix[0]:
        return []
    
    m, n = len(matrix), len(matrix[0])
    result = []
    row, col = 0, 0
    direction = 1  # 1 for up-right, -1 for down-left
    
    # Traverse all m*n elements
    for _ in range(m * n):
        result.append(matrix[row][col])
        
        if direction == 1:  # Moving up-right
            # Check if we hit top or right boundary
            if row == 0 and col < n - 1:
                col += 1
                direction = -1
            elif col == n - 1:
                row += 1
                direction = -1
            else:
                row -= 1
                col += 1
        else:  # Moving down-left (direction == -1)
            # Check if we hit left or bottom boundary
            if col == 0 and row < m - 1:
                row += 1
                direction = 1
            elif row == m - 1:
                col += 1
                direction = 1
            else:
                row += 1
                col -= 1
    
    return result

Start diagonal traverse of 3x3 matrix

0 / 29

Test Your Knowledge

Complexity Analysis

Time Complexity: O(m × n) We visit each cell exactly once, so time complexity is proportional to the total number of cells in the matrix

Space Complexity: O(1) We only use a constant amount of extra space for tracking current position and direction (excluding the output array)

Building Intuition

Every cell (i, j) in the matrix belongs to a diagonal identified by i+j. All cells with the same i+j value lie on the same diagonal line.

For a 3×3 matrix, diagonal 0 has cells where i+j=0 (just (0,0)), diagonal 1 has i+j=1 (cells (0,1) and (1,0)), diagonal 2 has i+j=2 (cells (0,2), (1,1), (2,0)), and so on.

The zigzag pattern means we traverse even-numbered diagonals in one direction and odd-numbered diagonals in the opposite direction.

By grouping cells by their diagonal index i+j, we can collect all elements that belong together. Then, we simply need to reverse every other group to create the alternating traversal pattern.

This transforms a complex 2D traversal problem into a simpler problem of: (1) group by diagonal, (2) conditionally reverse groups, (3) flatten the result.

Imagine walking through a parking lot with diagonal parking spaces. You could walk down one diagonal row, then walk up the next diagonal row, alternating your direction.

Instead of tracking complex movement rules (when to go right, when to go down, when to go diagonal), we can pre-organize all the parking spaces by which diagonal they belong to, then simply decide which diagonals to traverse forward vs backward.

The i+j sum naturally groups cells into diagonals, and the parity (even/odd) of this sum tells us which direction to traverse that diagonal.

Common Mistakes

Trying to simulate the zigzag movement with complex if-else chains for boundary conditions - this leads to hard-to-debug off-by-one errors and missed edge cases

Forgetting to reverse odd-numbered diagonals - this results in all diagonals being traversed in the same direction, breaking the zigzag pattern

Not handling single-row or single-column matrices correctly - these edge cases have degenerate diagonal structures that need special attention

Using the wrong diagonal index formula - some might try i-j instead of i+j, which groups anti-diagonals instead of diagonals

Incorrectly determining which diagonals to reverse - mixing up even/odd parity or using the wrong starting direction leads to incorrect output order

Optimal Solution

The optimal approach groups cells by their diagonal index i+j. Iterate through the matrix once, placing each element into a bucket corresponding to its diagonal (using a hash map or array of lists). Since there are at most m+n-1 diagonals, we create that many groups. After grouping, iterate through the diagonals in order: for even-indexed diagonals, append elements in their natural order; for odd-indexed diagonals, reverse the order before appending. This eliminates complex boundary logic and makes the alternating pattern explicit and easy to implement.

Visualization

def diagonal_order(matrix):
    """
    Return elements of m×n matrix in diagonal zigzag order.
    Groups cells by diagonal index (i+j), reverses odd diagonals.
    """
    if not matrix or not matrix[0]:
        return []
    
    m, n = len(matrix), len(matrix[0])
    max_diagonals = m + n - 1
    
    # Group cells by diagonal index (i+j)
    diagonals = [[] for _ in range(max_diagonals)]
    
    # Iterate through matrix and group by diagonal
    for i in range(m):
        for j in range(n):
            diagonal_index = i + j
            diagonals[diagonal_index].append(matrix[i][j])
    
    result = []
    
    # Process diagonals: reverse odd-indexed ones
    for idx in range(max_diagonals):
        if idx % 2 == 1:
            # Odd diagonal: reverse before adding
            diagonals[idx].reverse()
        result.extend(diagonals[idx])
    
    return result

Start diagonal traversal of matrix

0 / 40

Test Your Knowledge

Complexity Analysis

Time Complexity: O(m × n) We iterate through all m×n cells once to group them, then iterate through all groups to build the result. Both passes are linear in the total number of cells.

Space Complexity: O(m × n) We store all m×n elements in intermediate data structures (hash map or array of lists) to group them by diagonal before building the final result

What We've Learned

Diagonal grouping by coordinate sum: Elements on the same diagonal share the same i+j sum - this mathematical property transforms a 2D traversal problem into grouping by a single index, making complex zigzag patterns manageable through simple arithmetic.
Alternating direction with modulo: Use (diagonal_index % 2) to determine traversal direction - even diagonals go up-right (reverse order), odd diagonals go down-left (natural order). This eliminates complex conditional logic and makes the pattern predictable.
Boundary-aware diagonal length calculation: Each diagonal's length is min(diagonal_index + 1, m + n - diagonal_index - 1) capped by matrix dimensions - understanding this prevents out-of-bounds errors and correctly handles shorter diagonals at corners.
Collection-then-reverse vs in-place: Collecting all diagonal elements first, then conditionally reversing is cleaner than trying to traverse in the correct order initially - separation of concerns makes the code more maintainable and less error-prone.
Space-time tradeoff consideration: Using O(min(m,n)) auxiliary space to store one diagonal at a time is acceptable here because it simplifies logic significantly - sometimes a small space cost yields much cleaner, bug-free code than a pure O(1) solution.
Matrix traversal pattern generalization: The coordinate sum grouping technique extends to any diagonal-based matrix problem (anti-diagonals, spiral traversals, toeplitz matrices) - recognizing when row+column arithmetic creates useful groupings is a powerful matrix manipulation skill.

Test Your Understanding

Why is matrix the right data structure for this problem?

matrix provides the optimal access pattern

It's the only data structure that works

It's the easiest to implement

It uses the least memory

Select an answer to see the explanation

Question Timeline

See when this question was last asked and where, including any notes left by other candidates.

Company

Level

Region

Early November, 2025

Meta

Senior

Mid October, 2025

Meta

Mid-level

Early October, 2025

Meta

Mid-level

Get Premium to View All 8 Reports

Comments

Your account is free and you can post anonymously if you choose.

Hello Interview Premium

Recent interview questions

System Design Guided Practice

Exclusive content

Learn More

Leetcode 498. Diagonal Traverse

DESCRIPTION

Understanding the Problem

Brute Force Approach

Test Your Knowledge

Complexity Analysis

Building Intuition

Common Mistakes

Optimal Solution

Test Your Knowledge

Complexity Analysis

What We've Learned

Related Concepts and Problems to Practice

Test Your Understanding

Question Timeline

Comments

Questions

Learn

Links

Legal

Contact