March 24
Spiral Matrix
How to walk a matrix in layers using clear top bottom left right boundaries instead of scattered conditions.
Matrix Intermediate 20 min TypeScript
Given a matrix matrix, return all elements in spiral order.
Example:
Input:
matrix = [
[1,2,3],
[4,5,6],
[7,8,9]
]
Output: [1,2,3,6,9,8,7,4,5]
What to notice before coding
- The traversal happens in layers.
- Each layer can be described by four boundaries.
- The edge cases appear when only one row or one column remains.
Common mistakes
- forgetting to check whether a row or column still exists before walking the bottom or left side
- updating the boundaries in the wrong order and repeating elements
Step 1 - Understand the traversal by layers
Spiral order is not random.
It walks:
- the outer border
- then the next inner border
- and so on
This is a layer-by-layer traversal.
Step 2 - Write the most direct baseline
The natural baseline is:
- keep the current direction
- keep a visited matrix
- turn when you hit a boundary or a visited cell
It works.
But it carries more state than necessary.
Step 3 - Ask what state really matters
For the current layer, it is enough to know:
topbottomleftright
Those four boundaries describe exactly the rectangle that is still unvisited.
Step 4 - Walk and shrink
In each round:
- walk the top
- walk the right
- if a row still remains, walk the bottom
- if a column still remains, walk the left
Then shrink the boundaries.
The interactive editor needs JavaScript. You can still read the prompt and copy the starter code below.
Starter code
export function spiralOrder(matrix: number[][]): number[] {
// your solution here
return []
}
Haven't solved it yet?
Viewing the solution now may reduce learning. It's worth trying a bit more.
Open the reference solution
Without JavaScript, the reference solution is shown inline instead of in a dialog.
Solution
Final complexity
Time: O(m * n)
Space: O(1)
Solution 1 - Simulation with visited cells
Good baseline because it makes the traversal explicit.
export function spiralOrder(matrix: number[][]): number[] {
const rows = matrix.length
const cols = matrix[0].length
const visited = Array.from({ length: rows }, () => new Array(cols).fill(false))
const result: number[] = []
const directions = [[0, 1], [1, 0], [0, -1], [-1, 0]]
let directionIndex = 0
let row = 0
let col = 0
for (let count = 0; count < rows * cols; count += 1) {
result.push(matrix[row][col])
visited[row][col] = true
const nextRow = row + directions[directionIndex][0]
const nextCol = col + directions[directionIndex][1]
const outOfBounds = nextRow < 0 || nextRow >= rows || nextCol < 0 || nextCol >= cols
if (outOfBounds || visited[nextRow][nextCol]) {
directionIndex = (directionIndex + 1) % 4
}
row += directions[directionIndex][0]
col += directions[directionIndex][1]
}
return result
}It works, but there is a cleaner model for this kind of traversal.
Solution 2 - Boundaries
Now you walk the current layer and shrink the remaining rectangle.
export function spiralOrder(matrix: number[][]): number[] {
const result: number[] = []
let top = 0
let bottom = matrix.length - 1
let left = 0
let right = matrix[0].length - 1
while (top <= bottom && left <= right) {
for (let col = left; col <= right; col += 1) {
result.push(matrix[top][col])
}
top += 1
for (let row = top; row <= bottom; row += 1) {
result.push(matrix[row][right])
}
right -= 1
if (top <= bottom) {
for (let col = right; col >= left; col -= 1) {
result.push(matrix[bottom][col])
}
bottom -= 1
}
if (left <= right) {
for (let row = bottom; row >= top; row -= 1) {
result.push(matrix[row][left])
}
left += 1
}
}
return result
}The strong insight here is using the boundaries as a representation of the remaining problem.
What to say in the interview
A strong short explanation would be:
The baseline uses current direction plus a visited matrix, but that carries too much state. The stronger version represents the current layer with four boundaries:
top,bottom,left, andright. I walk the four borders that still exist and then shrink those boundaries, keeping onlyO(1)extra state.
That shows that you:
- simplified the state
- thought in layers instead of loose movement
- handled the remaining-row and remaining-column edge cases
When this pattern shows up again
This pattern comes back when you need to:
- traverse a matrix by layers
- maintain clear boundaries
- do simulation with minimal state
The point is not memorizing
Spiral Matrix.
The point is learning to model what is still left to traverse.