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.