Traverse a Matrix in Clockwise Spiral Order

Implement spiral_order(matrix) for a rectangular matrix.

Return all values in clockwise spiral order, beginning at the top-left corner and first moving right. An empty matrix returns an empty list. The input is not modified.

For example, [[1,2,3],[4,5,6],[7,8,9]] returns [1,2,3,6,9,8,7,4,5].

Target O(rows * columns) time and auxiliary space beyond the returned list that does not grow with the matrix dimensions.

Hint: Maintain four live boundaries

Track the top, bottom, left, and right edges of the unvisited rectangle, shrinking one boundary after traversing each side.

Hint: Guard the final two sides

Before traversing right-to-left or bottom-to-top, verify that both corresponding boundaries still describe an unvisited row or column. This prevents duplicate output for a single remaining row or column.

Discussion Extensions

• How would the traversal order change for a counterclockwise spiral?
• How would you reuse the boundary framework to fill an n by n matrix in spiral order?

Traverse a Matrix in Clockwise Spiral Order

Constraints

• The matrix is empty or rectangular with at least one row and one column.
• The matrix contains at most 100 cells.
• Each value is an integer from -1,000,000,000 through 1,000,000,000.

Examples

Example 1

Input: ([[1, 2, 3], [4, 5, 6], [7, 8, 9]],)
Output: [1, 2, 3, 6, 9, 8, 7, 4, 5]

Example 2

Input: ([[1, 2, 3], [4, 5, 6]],)
Output: [1, 2, 3, 6, 5, 4]

Hints

1. Track the top, bottom, left, and right boundaries of the unvisited rectangle.
2. Guard the bottom and left traversals after shrinking boundaries so a final row or column is not emitted twice.

Approach

Traverse the current top row and right column, then traverse the bottom row and left column only if they remain unvisited. Shrinking four boundaries after their corresponding sides are consumed visits every cell exactly once without a visited matrix.

• Time complexity: O(rows * columns)
• Space complexity: O(1) auxiliary space excluding the returned list