Traverse a Matrix in Clockwise Spiral Order
Company: Microsoft
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
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?
Overview: Traverse a rectangular matrix in clockwise spiral order without modifying the input. Learn the four-boundary technique and the guards that prevent duplicate visits on the final row or column.
Read the full Microsoft Software Engineer interview experience this question came from
Implement spiral_order(matrix). Return every value of a rectangular integer matrix in clockwise spiral order, starting at the top-left and moving right. Return an empty list for an empty matrix and do not modify the input.
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
Input: ([[1, 2, 3], [4, 5, 6], [7, 8, 9]],)
Expected Output: [1, 2, 3, 6, 9, 8, 7, 4, 5]
Input: ([[1, 2, 3], [4, 5, 6]],)
Expected Output: [1, 2, 3, 6, 5, 4]
Hints
- Track the top, bottom, left, and right boundaries of the unvisited rectangle.
- Guard the bottom and left traversals after shrinking boundaries so a final row or column is not emitted twice.