Traverse a Matrix in Spiral Order

Problem

Given an m x n matrix, return all elements in clockwise spiral order. Begin at the top-left corner, move right across the current top boundary, then down, left, and up while shrinking the remaining boundaries.

Implement:

def spiral_order(matrix: list[list[int]]) -> list[int]:
    ...

Constraints

• 0 <= m, n <= 200
• The matrix is rectangular when non-empty.
• Matrix values are signed integers.
• An empty matrix or a matrix with zero columns returns an empty list.
• Visit every element exactly once.

Examples

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

[[1, 2, 3, 4]]
-> [1, 2, 3, 4]

[[1], [2], [3]]
-> [1, 2, 3]

Performance Goal

Use O(m*n) time and O(1) auxiliary space apart from the returned list. Take care not to duplicate the final row or column when only one boundary remains.

Traverse a Matrix in Spiral Order

Hints

1. Track top, bottom, left, and right inclusive boundaries.
2. After traversing two sides, check whether a row or column remains before traversing back.
3. Shrink a boundary immediately after consuming it.

Approach

Four inclusive boundaries delimit the unvisited rectangle. Traverse its exposed top and right sides, then traverse bottom and left only if they still exist. Shrinking after each side prevents duplicating a final row or column.

• Time complexity: O(m * n).
• Space complexity: O(1) auxiliary space beyond the returned list.