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 ```python 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** ```text Input: matrix = [ [7, 1, 4], [3, 9, 2], [6, 5, 8] ] Output: [7, 1, 4, 2, 8, 5, 6, 3, 9] ``` **Example 2** ```text 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** ```text 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.