Clockwise Spiral Traversal of a Matrix With O(1) Extra Space and No Mutation
Company: ByteDance
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
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.
Overview: From a TikTok backend intern interview: return the elements of an m x n matrix in clockwise spiral order using only constant extra space beyond the output, without a visited marker and without modifying the matrix. It tests careful traversal logic and off-by-one handling when a single row or column remains.
Read the full ByteDance Software Engineer interview experience this question came from
Given an `m x n` integer matrix `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.
Implement `spiral_order(matrix)`. It returns a list of exactly `m * n` integers: the cell values in the order they are visited.
The interviewer added two follow-up restrictions, and both are requirements here:
- The traversal may use only `O(1)` extra space beyond the returned list, so no visited matrix and no visited set.
- The input matrix must not be modified, not even temporarily (for example, by overwriting visited cells with a marker value).
### 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` (so every row has the same length)
- `-1000 <= matrix[i][j] <= 1000`
- No value can exceed `2^31 - 1` in magnitude, so a 32-bit `int` suffices in every language; the result holds at most 10,000 values.
### Example 1
```text
Input: matrix = [
[7, 1, 4],
[3, 9, 2],
[6, 5, 8]
]
Output: [7, 1, 4, 2, 8, 5, 6, 3, 9]
```
The outer ring is read clockwise from the top-left cell (`7, 1, 4, 2, 8, 5, 6, 3`), and the single remaining center cell `9` comes last.
### 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.
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
- Use only O(1) extra space beyond the returned list, and do not modify matrix, not even temporarily
Examples
Input: ([[5]],)
Expected Output: [5]
Explanation: Minimum 1 x 1 matrix: the only cell is the whole spiral.
Input: ([[3, -1, 0, 2]],)
Expected Output: [3, -1, 0, 2]
Explanation: Single row (1 x 4) is read left to right; nothing is emitted twice.
Hints
- No visited set and no marker values are allowed, so think about how a handful of integers could describe exactly which cells are still unread.
- After one complete clockwise lap, what shape is the unread region, and how does it relate to the region before the lap?
- The rules single out a remaining single row and a remaining single column; check that each of their cells is emitted exactly once and in the stated direction.