Spiral Matrix
Spiral Matrix is a medium Math & Geometry problem from the Blind 75. The key pattern is shrinking boundaries, and a good solution runs in O(m · n) time.
Problem
Return matrix values in clockwise spiral order starting at the top-left.
Examples
Example 1
Input
[[1,2,3],[4,5,6],[7,8,9]]Output
[1,2,3,6,9,8,7,4,5]Example 2
Input
[[1,2,3,4],[5,6,7,8],[9,10,11,12]]Output
[1,2,3,4,8,12,11,10,9,5,6,7]Example 3
Input
[[7],[9],[6]]Output
[7,9,6]Approach
Keep top, bottom, left and right bounds, read one edge at a time and move the matching bound inward.
| Pattern | Shrinking boundaries |
|---|---|
| Time | O(m · n) |
| Space | O(1) beyond the output |
Watch out for
Re-check the bounds before the bottom and left passes so single rows or columns are not read twice.