Clockwise Spiral Traversal of a Matrix With O(1) Extra Space and No Mutation

Given an m x n integer matrix, return all of its elements in spiral order. Start at the top-left cell, move right along the top row, then down the right column, then left along the bottom row, then up the left column, and keep going clockwise, layer by layer, toward the center until every cell has been visited exactly once.

As a follow-up, the interviewer added two restrictions, and both are requirements here. First, the traversal may use only O(1) extra space beyond the returned list, so no visited matrix or visited set. Second, the input matrix must not be modified, not even temporarily, for example by overwriting visited cells with a marker value.

Function Signature

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

Rules

• Every cell appears in the output exactly once.
• When the unvisited region is a single row, it is read from left to right. When it is a single column, it is read from top to bottom.
• matrix must be identical after the call to what it was before the call.

Constraints

• 1 <= m <= 100 and 1 <= n <= 100, where m = len(matrix) and n = len(matrix[i]) for every row i
• -1000 <= matrix[i][j] <= 1000

Examples

Example 1

Input: matrix = [
 [7, 1, 4],
 [3, 9, 2],
 [6, 5, 8]
]
Output: [7, 1, 4, 2, 8, 5, 6, 3, 9]

Example 2

Input: matrix = [
 [1, 2, 3, 4, 5],
 [6, 7, 8, 9, 10],
 [11, 12, 13, 14, 15]
]
Output: [1, 2, 3, 4, 5, 10, 15, 14, 13, 12, 11, 6, 7, 8, 9]

After the outer layer, the remaining region is the single row 7, 8, 9, read from left to right.

Example 3

Input: matrix = [
 [1, 2, 3],
 [4, 5, 6],
 [7, 8, 9],
 [10, 11, 12]
]
Output: [1, 2, 3, 6, 9, 12, 11, 10, 7, 4, 5, 8]

After the outer layer, the remaining region is the single column 5, 8, read from top to bottom.