Traverse a Matrix in Spiral Order
Company: Pinduoduo
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
# Traverse a Matrix in Spiral Order
## Problem
Given an `m x n` matrix, return all elements in clockwise spiral order. Begin at the top-left corner, move right across the current top boundary, then down, left, and up while shrinking the remaining boundaries.
Implement:
```python
def spiral_order(matrix: list[list[int]]) -> list[int]:
...
```
## Constraints
- `0 <= m, n <= 200`
- The matrix is rectangular when non-empty.
- Matrix values are signed integers.
- An empty matrix or a matrix with zero columns returns an empty list.
- Visit every element exactly once.
## Examples
```text
[[1, 2, 3],
[4, 5, 6],
[7, 8, 9]]
-> [1, 2, 3, 6, 9, 8, 7, 4, 5]
[[1, 2, 3, 4]]
-> [1, 2, 3, 4]
[[1], [2], [3]]
-> [1, 2, 3]
```
## Performance Goal
Use `O(m*n)` time and `O(1)` auxiliary space apart from the returned list. Take care not to duplicate the final row or column when only one boundary remains.
Overview: Traverse a rectangular matrix in clockwise spiral order using shrinking boundaries. Handle empty, single-row, and single-column inputs without duplicates while achieving linear time and constant auxiliary space beyond the result.
Return every element of a rectangular matrix in clockwise spiral order, starting at the top-left and repeatedly traversing right, down, left, and up while shrinking the remaining boundaries.
Constraints
- The matrix is rectangular when nonempty.
- An empty matrix or zero-column matrix returns an empty list.
- Visit every element exactly once.
- Matrix values are signed integers.
- Use O(1) auxiliary space apart from the output.
Examples
Input: ([],)
Expected Output: []
Explanation: An empty matrix has no elements.
Input: ([[]],)
Expected Output: []
Explanation: A zero-column matrix has no elements.
Hints
- Track top, bottom, left, and right inclusive boundaries.
- After traversing two sides, check whether a row or column remains before traversing back.
- Shrink a boundary immediately after consuming it.