Spiral matrix: read a matrix in clockwise spiral order

Given an m x n integer matrix, return all of its elements in clockwise spiral order: walk the outer boundary clockwise starting at the top-left cell (top row left to right, right column downward, bottom row right to left, left column upward), then move one layer in and repeat until every cell has been visited once.

Interface

Unless you agree on a different interface with the interviewer, assume:

• spiral_order(matrix: list[list[int]]) -> list[int] — an empty matrix returns [].

Example

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

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

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

Constraints

• 0 <= m, n <= 100, and all rows have the same length.

Clarifying questions

• Can the matrix be empty, or have empty rows?
• Is the matrix always rectangular?
• May I modify the input to mark visited cells?

What a strong answer covers

• Four boundaries (top, bottom, left, right) that shrink after each side is walked.
• The checks that stop a single remaining row or column from being visited twice: walk the bottom row only if top <= bottom, and the left column only if left <= right.
• O(m * n) time and O(1) extra space beyond the output.
• Tests: a single row, a single column, a 1 x 1 matrix, a wide and a tall rectangle, an empty matrix.

Follow-ups

• Generate an n x n matrix filled with 1..n^2 in spiral order.
• Walk the spiral counterclockwise, or start from the center and spiral outward.
• Return the spiral one element at a time as an iterator, without building the full list.