Practice/Microsoft/Leetcode 54. Spiral Matrix

Leetcode 54. Spiral Matrix

CodingMust

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