Leetcode 54. Spiral Matrix

Problem

Given an m × n matrix of integers, return all elements of the matrix in diagonal order as shown below.

The diagonal traversal starts from the top-left corner and moves diagonally. When a diagonal is complete, you switch direction for the next diagonal. The pattern alternates between moving upward-right and downward-left along diagonals.

For example, in a 3×3 matrix, you would traverse:

• First diagonal going up: bottom-left to top-right
• Second diagonal going down: top-right to bottom-left
• Continue alternating until all elements are visited

Requirements

1. Return all matrix elements in a single array following the diagonal traversal pattern
2. Alternate the direction of traversal for each diagonal
3. Handle rectangular matrices (where rows ≠ columns)
4. Visit each element exactly once

Constraints

• m == matrix.length
• n == matrix[i].length
• 1 <= m, n <= 100
• -100 <= matrix[i][j] <= 100
• Time complexity should be O(m × n)
• Space complexity should be O(1) excluding the output array

Examples

Example 1:

Input: matrix = [[1,2,3],[4,5,6],[7,8,9]] Output: [1,2,4,7,5,3,6,8,9] Explanation: Diagonal 1 (up): [1] Diagonal 2 (down): [2, 4] Diagonal 3 (up): [7, 5, 3] Diagonal 4 (down): [6, 8] Diagonal 5 (up): [9]

Example 2:

Input: matrix = [[1,2],[3,4]] Output: [1,2,3,4] Explanation: Diagonal 1 (up): [1] Diagonal 2 (down): [2, 3] Diagonal 3 (up): [4]

Example 3:

Input: matrix = [[1,2,3,4],[5,6,7,8]] Output: [1,2,5,6,3,4,7,8] Explanation: The diagonals alternate direction in a 2x4 matrix

Hint 1: Understanding Diagonals Elements on the same diagonal share a common property: the sum of their row and column indices is constant. For example, in a matrix, elements at positions (0,2), (1,1), and (2,0) all have row+col = 2.

Think about how you can group elements by this sum, then process each group in the appropriate direction.

Hint 2: Direction Pattern Notice that diagonals alternate between going "up-right" and "down-left". You can determine the direction based on whether the diagonal number (sum of indices) is even or odd.

When moving up-right, you process elements with decreasing row index. When moving down-left, you process elements with increasing row index.

Hint 3: Implementation Strategy Consider iterating through all possible diagonal sums from 0 to (m + n - 2). For each diagonal sum, collect all valid cells where row + col equals that sum, ensuring row and col are within matrix bounds.

Then reverse the order of elements for every other diagonal to achieve the alternating direction pattern.

Full Solution ` def findDiagonalOrder(matrix): # Handle empty matrix if not matrix or not matrix[0]: return []

m, n = len(matrix), len(matrix[0])
result = []

# There are m + n - 1 diagonals in total
# Each diagonal is identified by the sum of row and column indices
for diagonal_sum in range(m + n - 1):
    # Collect all elements in this diagonal
    diagonal_elements = []
    
    # For a given diagonal_sum, find all valid (row, col) pairs
    # where row + col = diagonal_sum
    for row in range(m):
        col = diagonal_sum - row
        # Check if column is within bounds
        if 0 <= col < n:
            diagonal_elements.append(matrix[row][col])
    
    # Reverse every other diagonal (even-indexed diagonals go upward)
    if diagonal_sum % 2 == 0:
        diagonal_elements.reverse()
    
    # Add all elements from this diagonal to result
    result.extend(diagonal_elements)

return result

`

Explanation:

The solution works by recognizing that elements on the same diagonal share a common sum of their row and column indices.

Algorithm:

1. Calculate the total number of diagonals: m + n - 1

2. For each diagonal (identified by the sum of indices from 0 to m+n-2):

   • Iterate through all rows
   • Calculate the corresponding column as diagonal_sum - row
   • If the column is valid (within bounds), add the element to the current diagonal

3. Reverse elements in even-indexed diagonals to achieve the alternating direction

4. Append all diagonal elements to the result array

Time Complexity: O(m × n) - we visit each element exactly once

Space Complexity: O(min(m, n)) - at most, a diagonal contains min(m, n) elements in temporary storage. The output array is not counted toward space complexity.

Alternative Approach:

You could also solve this by simulating the actual diagonal walk with direction changes, tracking current position and direction, and handling boundary conditions. However, the diagonal-sum approach is cleaner and easier to implement correctly.