Spiral Matrix
Description
Given a 2D matrix of size m × n (m rows and n columns), your task is to collect every element in the matrix by traversing it in a spiral pattern and return them as a single list.
The spiral pattern works as follows: start from the top-left corner, move right across the first row, then move down the last column, then move left across the bottom row, then move up the first column. After completing one full loop around the outer boundary, move inward and repeat the same pattern on the remaining inner sub-matrix until every element has been visited.
The result should contain all m × n elements in exactly the order they were visited during this spiral traversal.
Examples
Example 1
Input: matrix = [[1,2,3],[4,5,6],[7,8,9]]
Output: [1,2,3,6,9,8,7,4,5]
Explanation: Starting at the top-left corner (value 1), we traverse right across the top row collecting 1, 2, 3. Then we move down the rightmost column collecting 6, 9. Next we go left across the bottom row collecting 8, 7. Then we go up the leftmost column collecting 4. Finally we move inward and collect the remaining center element 5. The spiral sweeps the outer boundary first, then peels inward layer by layer.
Example 2
Input: matrix = [[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]
Explanation: The matrix is 3 rows by 4 columns. We traverse right across the top row: 1, 2, 3, 4. Then down the right column: 8, 12. Then left across the bottom row: 11, 10, 9. Then up the left column: 5. Now the outer boundary is fully consumed. The remaining inner part is just one row [6, 7], which we traverse left to right: 6, 7. This illustrates how non-square matrices work — the inner portion may be a single row or a single column.
Example 3
Input: matrix = [[7],[9],[6]]
Output: [7,9,6]
Explanation: This is a single-column matrix (3×1). The spiral traversal simply moves down the only column: 7, 9, 6. There are no left or right turns needed because there is only one column. This edge case shows that spiral traversal gracefully handles degenerate shapes.
Constraints
- m == matrix.length
- n == matrix[i].length
- 1 ≤ m, n ≤ 10
- -100 ≤ matrix[i][j] ≤ 100
Editorial
Brute Force
Intuition
The most straightforward way to simulate a spiral traversal is to literally walk through the matrix step by step, keeping track of which cells we have already visited.
Imagine you are walking through a maze shaped like a rectangular room. You start at the top-left corner facing right. You keep walking forward until you either hit a wall (the boundary of the matrix) or step on a tile you have already walked on. When that happens, you turn right (change direction from right → down → left → up → right → ...) and continue. You keep doing this until you have stepped on every tile exactly once.
To implement this, we maintain a visited matrix of the same dimensions. We also define four direction vectors — right, down, left, up — and cycle through them whenever we need to turn. At each step, we check if the next cell in the current direction is valid (within bounds and not yet visited). If it is, we move there. If not, we turn clockwise and try again.
Step-by-Step Explanation
Let's trace through with matrix = [[1,2,3],[4,5,6],[7,8,9]]:
Step 1: Initialize position at (0,0), direction = right. Mark (0,0) as visited. Collect value 1. Result: [1].
Step 2: Move right to (0,1). Mark visited. Collect 2. Result: [1,2].
Step 3: Move right to (0,2). Mark visited. Collect 3. Result: [1,2,3].
Step 4: Try to move right to (0,3) — out of bounds! Turn clockwise to face down. Move down to (1,2). Mark visited. Collect 6. Result: [1,2,3,6].
Step 5: Move down to (2,2). Mark visited. Collect 9. Result: [1,2,3,6,9].
Step 6: Try to move down to (3,2) — out of bounds! Turn clockwise to face left. Move left to (2,1). Mark visited. Collect 8. Result: [1,2,3,6,9,8].
Step 7: Move left to (2,0). Mark visited. Collect 7. Result: [1,2,3,6,9,8,7].
Step 8: Try to move left to (2,-1) — out of bounds! Turn clockwise to face up. Move up to (1,0). Mark visited. Collect 4. Result: [1,2,3,6,9,8,7,4].
Step 9: Try to move up to (0,0) — already visited! Turn clockwise to face right. Move right to (1,1). Mark visited. Collect 5. Result: [1,2,3,6,9,8,7,4,5].
Step 10: All 9 cells visited. Return [1,2,3,6,9,8,7,4,5].
Spiral Matrix — Simulation with Visited Tracking — Watch how we walk through the grid cell by cell, turning clockwise whenever we hit a boundary or an already-visited cell.
Algorithm
- Create a visited matrix of the same dimensions, initialized to false
- Define four direction vectors: right (0,1), down (1,0), left (0,-1), up (-1,0)
- Start at position (0,0) with direction index 0 (right)
- Repeat m × n times:
a. Collect the value at the current position and mark it visited
b. Compute the next position using the current direction
c. If the next position is out of bounds or already visited, turn clockwise (direction index = (direction index + 1) % 4) and recompute the next position
d. Move to the next position - Return the collected values
Code
class Solution {
public:
vector<int> spiralOrder(vector<vector<int>>& matrix) {
int m = matrix.size();
int n = matrix[0].size();
vector<vector<bool>> visited(m, vector<bool>(n, false));
// Direction vectors: right, down, left, up
int dr[] = {0, 1, 0, -1};
int dc[] = {1, 0, -1, 0};
vector<int> result;
int r = 0, c = 0, dir = 0;
for (int i = 0; i < m * n; i++) {
result.push_back(matrix[r][c]);
visited[r][c] = true;
int nextR = r + dr[dir];
int nextC = c + dc[dir];
// If next cell is invalid, turn clockwise
if (nextR < 0 || nextR >= m || nextC < 0 || nextC >= n || visited[nextR][nextC]) {
dir = (dir + 1) % 4;
nextR = r + dr[dir];
nextC = c + dc[dir];
}
r = nextR;
c = nextC;
}
return result;
}
};class Solution:
def spiralOrder(self, matrix: list[list[int]]) -> list[int]:
m = len(matrix)
n = len(matrix[0])
visited = [[False] * n for _ in range(m)]
# Direction vectors: right, down, left, up
dr = [0, 1, 0, -1]
dc = [1, 0, -1, 0]
result = []
r, c, direction = 0, 0, 0
for _ in range(m * n):
result.append(matrix[r][c])
visited[r][c] = True
next_r = r + dr[direction]
next_c = c + dc[direction]
# If next cell is invalid, turn clockwise
if (next_r < 0 or next_r >= m or next_c < 0
or next_c >= n or visited[next_r][next_c]):
direction = (direction + 1) % 4
next_r = r + dr[direction]
next_c = c + dc[direction]
r, c = next_r, next_c
return resultclass Solution {
public List<Integer> spiralOrder(int[][] matrix) {
int m = matrix.length;
int n = matrix[0].length;
boolean[][] visited = new boolean[m][n];
// Direction vectors: right, down, left, up
int[] dr = {0, 1, 0, -1};
int[] dc = {1, 0, -1, 0};
List<Integer> result = new ArrayList<>();
int r = 0, c = 0, dir = 0;
for (int i = 0; i < m * n; i++) {
result.add(matrix[r][c]);
visited[r][c] = true;
int nextR = r + dr[dir];
int nextC = c + dc[dir];
if (nextR < 0 || nextR >= m || nextC < 0 || nextC >= n || visited[nextR][nextC]) {
dir = (dir + 1) % 4;
nextR = r + dr[dir];
nextC = c + dc[dir];
}
r = nextR;
c = nextC;
}
return result;
}
}Complexity Analysis
Time Complexity: O(m × n)
We visit each of the m × n cells exactly once. At each cell, we perform constant-time work: appending to the result, marking visited, and checking one or two adjacent cells. The total number of operations is proportional to the total number of cells.
Space Complexity: O(m × n)
We use an m × n visited matrix to track which cells have been collected. This auxiliary space is the same size as the input matrix. The result array also takes O(m × n) space, but that is required for the output.
Why This Approach Is Not Efficient
While the simulation approach works correctly, it uses O(m × n) extra space for the visited matrix. For every single cell, we allocate a boolean flag just to remember whether we have been there before.
The key insight is that we do not actually need to track individual cells. The spiral pattern is highly structured: we always traverse along the current outermost boundary, then shrink inward. If we maintain four boundary variables (top, bottom, left, right), we can determine exactly which cells to visit next without ever checking a visited matrix. These four integers replace the entire m × n boolean grid.
This reduces auxiliary space from O(m × n) to O(1) — a significant improvement when the matrix is large.
Optimal Approach - Boundary Shrinking
Intuition
Instead of simulating each step and checking visited flags, we observe that the spiral pattern has a very predictable structure: it always processes the outermost ring of the matrix first, then the next inner ring, and so on.
Think of peeling an onion layer by layer. Each layer is a rectangular boundary defined by four edges — top row, right column, bottom row, left column. After we process all four edges of the current ring, the ring is consumed, and we "shrink" inward by adjusting our boundaries.
We maintain four variables:
- top: the index of the topmost unprocessed row
- bottom: the index of the bottommost unprocessed row
- left: the index of the leftmost unprocessed column
- right: the index of the rightmost unprocessed column
In each iteration of our loop, we:
- Traverse the top row from left to right, then increment top
- Traverse the right column from top to bottom, then decrement right
- If top ≤ bottom (rows remain), traverse the bottom row from right to left, then decrement bottom
- If left ≤ right (columns remain), traverse the left column from bottom to top, then increment left
The checks in steps 3 and 4 are important for non-square matrices where the remaining inner portion might be a single row or a single column, not a full ring.
Step-by-Step Explanation
Let's trace through with matrix = [[1,2,3],[4,5,6],[7,8,9]]:
Initial boundaries: top=0, bottom=2, left=0, right=2.
Step 1: Traverse top row (row 0) from left=0 to right=2: collect 1, 2, 3. Increment top to 1.
Step 2: Traverse right column (col 2) from top=1 to bottom=2: collect 6, 9. Decrement right to 1.
Step 3: Check top(1) ≤ bottom(2)? Yes. Traverse bottom row (row 2) from right=1 to left=0: collect 8, 7. Decrement bottom to 1.
Step 4: Check left(0) ≤ right(1)? Yes. Traverse left column (col 0) from bottom=1 to top=1: collect 4. Increment left to 1.
Boundaries now: top=1, bottom=1, left=1, right=1. Loop continues since top ≤ bottom and left ≤ right.
Step 5: Traverse top row (row 1) from left=1 to right=1: collect 5. Increment top to 2.
Step 6: Traverse right column (col 1) from top=2 to bottom=1: top > bottom, nothing to traverse. Decrement right to 0.
Now top(2) > bottom(1), so loop ends.
Result: [1, 2, 3, 6, 9, 8, 7, 4, 5].
Spiral Matrix — Boundary Shrinking Layer by Layer — Watch how four boundary pointers (top, bottom, left, right) define the current ring, shrinking inward after each edge is processed.
Algorithm
- Initialize four boundary variables: top = 0, bottom = m - 1, left = 0, right = n - 1
- While top ≤ bottom AND left ≤ right:
a. Traverse the top row from column left to column right → append each element. Increment top.
b. Traverse the right column from row top to row bottom → append each element. Decrement right.
c. If top ≤ bottom: traverse the bottom row from column right to column left → append each element. Decrement bottom.
d. If left ≤ right: traverse the left column from row bottom to row top → append each element. Increment left. - Return the result list
Code
class Solution {
public:
vector<int> spiralOrder(vector<vector<int>>& matrix) {
int m = matrix.size();
int n = matrix[0].size();
vector<int> result;
int top = 0, bottom = m - 1;
int left = 0, right = n - 1;
while (top <= bottom && left <= right) {
// Traverse top row: left to right
for (int col = left; col <= right; col++) {
result.push_back(matrix[top][col]);
}
top++;
// Traverse right column: top to bottom
for (int row = top; row <= bottom; row++) {
result.push_back(matrix[row][right]);
}
right--;
// Traverse bottom row: right to left (if rows remain)
if (top <= bottom) {
for (int col = right; col >= left; col--) {
result.push_back(matrix[bottom][col]);
}
bottom--;
}
// Traverse left column: bottom to top (if columns remain)
if (left <= right) {
for (int row = bottom; row >= top; row--) {
result.push_back(matrix[row][left]);
}
left++;
}
}
return result;
}
};class Solution:
def spiralOrder(self, matrix: list[list[int]]) -> list[int]:
m = len(matrix)
n = len(matrix[0])
result = []
top, bottom = 0, m - 1
left, right = 0, n - 1
while top <= bottom and left <= right:
# Traverse top row: left to right
for col in range(left, right + 1):
result.append(matrix[top][col])
top += 1
# Traverse right column: top to bottom
for row in range(top, bottom + 1):
result.append(matrix[row][right])
right -= 1
# Traverse bottom row: right to left (if rows remain)
if top <= bottom:
for col in range(right, left - 1, -1):
result.append(matrix[bottom][col])
bottom -= 1
# Traverse left column: bottom to top (if columns remain)
if left <= right:
for row in range(bottom, top - 1, -1):
result.append(matrix[row][left])
left += 1
return resultclass Solution {
public List<Integer> spiralOrder(int[][] matrix) {
int m = matrix.length;
int n = matrix[0].length;
List<Integer> result = new ArrayList<>();
int top = 0, bottom = m - 1;
int left = 0, right = n - 1;
while (top <= bottom && left <= right) {
// Traverse top row: left to right
for (int col = left; col <= right; col++) {
result.add(matrix[top][col]);
}
top++;
// Traverse right column: top to bottom
for (int row = top; row <= bottom; row++) {
result.add(matrix[row][right]);
}
right--;
// Traverse bottom row: right to left (if rows remain)
if (top <= bottom) {
for (int col = right; col >= left; col--) {
result.add(matrix[bottom][col]);
}
bottom--;
}
// Traverse left column: bottom to top (if columns remain)
if (left <= right) {
for (int row = bottom; row >= top; row--) {
result.add(matrix[row][left]);
}
left++;
}
}
return result;
}
}Complexity Analysis
Time Complexity: O(m × n)
Every element in the m × n matrix is visited exactly once across all the boundary traversal loops. The four for-loops per iteration of the while loop collectively process one ring of the matrix. Summing across all rings, the total number of elements processed is exactly m × n.
Space Complexity: O(1)
We use only four integer variables (top, bottom, left, right) to track the boundaries, regardless of the matrix size. The output array takes O(m × n) space, but this is required by the problem and not counted as auxiliary space. Compared to the simulation approach which needed an O(m × n) visited matrix, this is a significant improvement.