Leetcode 498. Diagonal Traverse

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?

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.

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

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.

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.

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

• 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.