Spiral Matrix
Java coding interview problem for Matrix Problems: Spiral Matrix.
The Spiral Matrix problem is one of the most popular matrix traversal problems in coding interviews.
Unlike normal matrix traversal:
Row by Row
or:
Column by Column
spiral traversal requires visiting elements in a circular pattern.
This problem helps understand:
- Matrix boundaries
- Direction changes
- Two-dimensional array traversal
- Index management
- Simulation algorithms
It is commonly asked in interviews at:
- Amazon
- Microsoft
- Meta
- Apple
What is Spiral Matrix Traversal?
Spiral traversal means visiting all elements of a matrix in a spiral order.
The traversal starts from:
Top-left corner
and moves:
Right
↓
Down
↓
Left
↓
Up
continuously until all elements are visited.
Example 1
Input:
[
[1,2,3],
[4,5,6],
[7,8,9]
]
Spiral Order:
1 → 2 → 3 → 6 → 9 → 8 → 7 → 4 → 5
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]
]
Spiral Order:
1
2
3
4
8
12
11
10
9
5
6
7
Output:
[1,2,3,4,8,12,11,10,9,5,6,7]
Understanding Matrix Traversal
Consider:
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
Normal traversal:
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
Spiral traversal:
Outer layer:
1 2 3 4 8 12 16 15 14 13 9 5
Inner layer:
6 7 11 10
Final:
1 2 3 4 8 12 16 15 14 13 9 5 6 7 11 10
Why Is Spiral Matrix Asked in Interviews?
This problem tests:
1. Boundary Management
Can you maintain:
top
bottom
left
right
boundaries?
2. Direction Control
Can you move correctly:
Right
Down
Left
Up
?
3. Edge Case Handling
Can you handle:
- Single row
- Single column
- Rectangular matrix
- Empty matrix
4. Algorithm Design
Can you avoid:
Extra memory
and solve efficiently?
Real-World Applications
Image Processing
Images are represented as matrices.
Spiral traversal can be used for:
- Pixel scanning
- Compression algorithms
- Image analysis
Game Development
Grid-based games use spiral movement for:
- Map exploration
- Search algorithms
- Pattern generation
Robotics
Robot movement patterns can follow spiral paths for:
- Area scanning
- Coverage algorithms
Data Visualization
Matrix-based reports can be displayed in different traversal patterns.
Problem Statement
Given an:
m × n matrix
return all elements in spiral order.
Example
Input:
[
[1,2,3],
[4,5,6],
[7,8,9]
]
Output:
[
1,2,3,6,9,8,7,4,5
]
Constraints
Example:
1 <= rows <= 100
1 <= columns <= 100
Important Observation
A matrix has four boundaries:
Top Boundary
Bottom Boundary
Left Boundary
Right Boundary
After visiting a boundary:
Shrink it
and continue.
Boundary Concept
For:
3 × 4 Matrix
Example:
1 2 3 4
5 6 7 8
9 10 11 12
Initial boundaries:
top = 0
bottom = 2
left = 0
right = 3
Spiral Movement Rules
Step 1 — Traverse Top Row
Move:
left → right
Then:
top++
Step 2 — Traverse Right Column
Move:
top → bottom
Then:
right--
Step 3 — Traverse Bottom Row
Move:
right → left
Then:
bottom--
Step 4 — Traverse Left Column
Move:
bottom → top
Then:
left++
Repeat until:
top > bottom
or
left > right
Matrix Visualization
Input:
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
First Layer:
Top:
1 2 3 4
Right:
8
12
16
Bottom:
15 14 13
Left:
9
5
Remaining:
6 7
10 11
Dry Run Example
Input:
1 2 3
4 5 6
7 8 9
Initial:
top = 0
bottom = 2
left = 0
right = 2
Traverse Top
Elements:
1 2 3
Result:
[1,2,3]
Update:
top = 1
Traverse Right
Elements:
6
9
Result:
[1,2,3,6,9]
Update:
right = 1
Traverse Bottom
Elements:
8 7
Result:
[1,2,3,6,9,8,7]
Update:
bottom = 1
Traverse Left
Element:
4
Result:
[1,2,3,6,9,8,7,4]
Update:
left = 1
Remaining center:
5
Result:
[1,2,3,6,9,8,7,4,5]
Approach 1 — Brute Force Using Visited Matrix
The simplest approach:
Maintain an additional matrix:
visited[][]
to track processed cells.
Algorithm
- Start at:
0,0
- Move in current direction.
- If next cell is invalid or visited:
- Change direction.
- Continue until all cells are visited.
Directions
Movement:
Right:
(0,+1)
Down:
(+1,0)
Left:
(0,-1)
Up:
(-1,0)
Java Program
import java.util.*;
public class SpiralMatrixVisited {
public static List<Integer> spiralOrder(
int[][] matrix) {
List<Integer> result =
new ArrayList<>();
if (matrix.length == 0) {
return result;
}
int rows =
matrix.length;
int cols =
matrix[0].length;
boolean[][] visited =
new boolean[rows][cols];
int[][] directions =
{
{0,1},
{1,0},
{0,-1},
{-1,0}
};
int row = 0;
int col = 0;
int direction = 0;
for (int i = 0;
i < rows * cols;
i++) {
result.add(
matrix[row][col]);
visited[row][col] = true;
int nextRow =
row + directions[direction][0];
int nextCol =
col + directions[direction][1];
if(nextRow < 0 ||
nextRow >= rows ||
nextCol < 0 ||
nextCol >= cols ||
visited[nextRow][nextCol]) {
direction =
(direction + 1) % 4;
nextRow =
row + directions[direction][0];
nextCol =
col + directions[direction][1];
}
row = nextRow;
col = nextCol;
}
return result;
}
}
Complexity Analysis
Every element is visited once.
Time:
O(rows × columns)
Space:
O(rows × columns)
because of:
visited matrix
Advantages
- Easy to understand.
- Direct simulation.
- Works for all matrices.
Drawbacks
- Extra memory required.
- Not optimal.
Approach 2 — Boundary Traversal Approach (Optimal)
The boundary traversal approach is the most efficient and commonly expected interview solution.
Instead of tracking visited cells, we maintain four boundaries:
top
bottom
left
right
As we complete each layer, we shrink the boundaries.
Core Idea
A matrix can be viewed as multiple layers.
Example:
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
Outer layer:
1 2 3 4 8 12 16 15 14 13 9 5
Inner layer:
6 7 11 10
Algorithm
Initialize:
top = 0
bottom = rows - 1
left = 0
right = columns - 1
Repeat while:
top <= bottom
AND
left <= right
Step 1 — Traverse Top Row
Move:
left → right
Add elements.
Then:
top++
Step 2 — Traverse Right Column
Move:
top → bottom
Add elements.
Then:
right--
Step 3 — Traverse Bottom Row
Move:
right → left
Add elements.
Then:
bottom--
Step 4 — Traverse Left Column
Move:
bottom → top
Add elements.
Then:
left++
Java Program
import java.util.ArrayList;
import java.util.List;
public class SpiralMatrixBoundary {
public static List<Integer> spiralOrder(
int[][] matrix) {
List<Integer> result =
new ArrayList<>();
if (matrix == null ||
matrix.length == 0) {
return result;
}
int rows =
matrix.length;
int columns =
matrix[0].length;
int top = 0;
int bottom = rows - 1;
int left = 0;
int right = columns - 1;
while (top <= bottom &&
left <= right) {
// Top row
for (int col = left;
col <= right;
col++) {
result.add(
matrix[top][col]);
}
top++;
// Right column
for (int row = top;
row <= bottom;
row++) {
result.add(
matrix[row][right]);
}
right--;
// Bottom row
if (top <= bottom) {
for (int col = right;
col >= left;
col--) {
result.add(
matrix[bottom][col]);
}
bottom--;
}
// Left column
if (left <= right) {
for (int row = bottom;
row >= top;
row--) {
result.add(
matrix[row][left]);
}
left++;
}
}
return result;
}
public static void main(String[] args) {
int[][] matrix =
{
{1,2,3},
{4,5,6},
{7,8,9}
};
System.out.println(
spiralOrder(matrix));
}
}
Output
[1, 2, 3, 6, 9, 8, 7, 4, 5]
Step-by-Step Explanation
Input:
1 2 3
4 5 6
7 8 9
Initial:
top = 0
bottom = 2
left = 0
right = 2
Top Row
Traverse:
1 2 3
Result:
[1,2,3]
Update:
top = 1
Right Column
Traverse:
6
9
Result:
[1,2,3,6,9]
Update:
right = 1
Bottom Row
Traverse:
8 7
Result:
[1,2,3,6,9,8,7]
Update:
bottom = 1
Left Column
Traverse:
4
Result:
[1,2,3,6,9,8,7,4]
Update:
left = 1
Remaining:
5
Result:
[1,2,3,6,9,8,7,4,5]
Complexity Analysis
Every matrix element is visited once.
For:
rows × columns
matrix:
Time:
O(rows × columns)
Space:
O(1)
(excluding output list)
Advantages
- Optimal solution.
- No visited matrix.
- Works for rectangular matrices.
- Interview preferred approach.
Drawbacks
- Requires careful boundary handling.
- Edge cases are tricky.
Spiral Traversal for Rectangular Matrix
The same algorithm works for:
m × n
matrices.
Example:
Input:
1 2 3 4
5 6 7 8
9 10 11 12
Traversal:
Top:
1 2 3 4
Right:
8 12
Bottom:
11 10 9
Left:
5
Inner:
6 7
Output:
[1,2,3,4,8,12,11,10,9,5,6,7]
Generate Matrix in Spiral Order
A common follow-up:
Generate an n × n matrix containing numbers from 1 to n² in spiral order.
Example
Input:
n = 3
Output:
1 2 3
8 9 4
7 6 5
Java Program
public class GenerateSpiralMatrix {
public static int[][] generate(
int n) {
int[][] matrix =
new int[n][n];
int top = 0;
int bottom = n - 1;
int left = 0;
int right = n - 1;
int value = 1;
while (top <= bottom &&
left <= right) {
for (int col = left;
col <= right;
col++) {
matrix[top][col] =
value++;
}
top++;
for (int row = top;
row <= bottom;
row++) {
matrix[row][right] =
value++;
}
right--;
if (top <= bottom) {
for (int col = right;
col >= left;
col--) {
matrix[bottom][col] =
value++;
}
bottom--;
}
if (left <= right) {
for (int row = bottom;
row >= top;
row--) {
matrix[row][left] =
value++;
}
left++;
}
}
return matrix;
}
}
Output Example
For:
n = 3
Result:
1 2 3
8 9 4
7 6 5
Reverse Spiral Traversal
Reverse spiral means:
Start from the center and move outward.
Example:
Normal:
1 2 3 6 9 8 7 4 5
Reverse:
5 4 7 8 9 6 3 2 1
Java Streams Approach
Streams are not recommended for spiral traversal.
Reason:
Spiral traversal requires:
- Mutable boundaries
- Direction changes
- Index tracking
Traditional loops are clearer.
A stream implementation would reduce readability.
Comparison of All Approaches
| Approach | Time Complexity | Space Complexity | Recommended |
|---|---|---|---|
| Visited Matrix | O(m×n) | O(m×n) | Learning |
| Boundary Traversal | O(m×n) | O(1) | Best Solution |
| Recursive Spiral | O(m×n) | O(min(m,n)) | Alternative |
| Streams | O(m×n) | O(m×n) | Not Recommended |
Matrix Index Mapping
Spiral traversal follows:
Direction 1
Right:
(row, col++)
Direction 2
Down:
(row++, col)
Direction 3
Left:
(row, col--)
Direction 4
Up:
(row--, col)
Primitive vs Object Arrays
Primitive Matrix
int[][]
Advantages:
- Faster.
- Less memory.
- Better cache performance.
Recommended for:
- Large matrices.
- Competitive programming.
Object Matrix
Integer[][]
Advantages:
- Supports Collections.
- Allows null values.
Disadvantages:
- Higher memory usage.
Common Interview Mistakes
Mistake 1
Forgetting boundary checks.
Example:
if(top <= bottom)
is required before bottom traversal.
Mistake 2
Duplicating center elements.
Happens in:
single row
single column
cases.
Mistake 3
Incorrect boundary updates.
Correct:
top++
right--
bottom--
left++
Mistake 4
Assuming only square matrices.
Spiral traversal works for:
rectangular matrices
Edge Cases
| Input | Output |
|---|---|
| Empty matrix | [] |
| Single element | [1] |
| Single row | All elements left to right |
| Single column | Top to bottom |
| 2×2 matrix | Works |
| Rectangular matrix | Works |
Interview Follow-up Questions
Q1. Print matrix in spiral order.
Q2. Generate spiral matrix.
Q3. Reverse spiral traversal.
Q4. Rotate matrix and print spiral.
Q5. Find kth element in spiral order.
Q6. Traverse matrix diagonally.
Q7. Search element in sorted matrix.
Related Problems
- Matrix Rotation
- Matrix Transpose
- Set Matrix Zeroes
- Search a 2D Matrix
- Flood Fill
- Number of Islands
- Diagonal Traversal
Key Takeaways
Spiral Matrix is a classic boundary traversal problem.
The evolution:
Visited Matrix
↓
Boundary Traversal
↓
Optimized Solution
Best interview approach:
Boundary Traversal
Complexity:
Time: O(rows × columns)
Space: O(1)
The most important concept:
Control the matrix boundaries carefully while shrinking the search area layer by layer.
Frequently Asked Interview Questions
Q1. What are the four boundaries?
top
bottom
left
right
Q2. Why use boundary traversal?
Because each element is visited exactly once without extra memory.
Q3. How do you handle a single row?
Only process top row.
Q4. How do you handle a single column?
Only process left/right column.
Q5. What is the complexity?
O(m × n)
because every element is visited once.
Interview Tip
When asked:
"Print matrix in spiral order."
Explain:
- Maintain four boundaries.
- Traverse four directions.
- Shrink boundaries after every layer.
- Add safety checks for remaining rows and columns.
This demonstrates strong understanding of matrix traversal, boundary control, and algorithm design.