Spiral Matrix II — Solution in Python, Java & C++
Spiral Matrix II solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem on arrays and matrix.
Spiral Matrix II is a medium coding problem on arrays, matrix and simulation, asked in Amazon, Microsoft and Adobe interviews.
- Difficulty: Medium
- Topics: Arrays, Matrix, Simulation
- Asked at: Amazon, Microsoft, Adobe
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Given a positive integer n, generate an n × n matrix filled with the numbers 1 to n² in spiral order, starting at the top-left corner and moving right.
Example 1
Input: n = 3
Output: [[1,2,3],[8,9,4],[7,6,5]]
Example 2
Input: n = 1
Output: [[1]]
Example 3
Input: n = 2
Output: [[1,2],[4,3]]
Constraints
1 <= n <= 9
Hints for Spiral Matrix II
Hint 1
Keep four boundaries — top, bottom, left, right — and shrink one after each pass.
Hint 2
Walk right along the top row, down the right column, left along the bottom, up the left column, then repeat.
Hint 3
Re-check the boundaries before the bottom and left passes; on an odd-sized spiral the last ring is a single row or column.
How to solve Spiral Matrix II
Keep four boundaries and fill the outer ring in four passes — right along the top, down the right, left along the bottom, up the left — shrinking a boundary after each pass.
Approach
- Set
top = 0,bottom = n - 1,left = 0,right = n - 1and a counterv = 1. - While
top <= bottomandleft <= right: fill rowtopfromlefttoright, thentop++; fill columnrightfromtoptobottom, thenright--. - If
top <= bottom, fill rowbottomright-to-left andbottom--; ifleft <= right, fill columnleftbottom-to-top andleft++.
Why it works
Each pass writes exactly the cells of one edge of the current unfilled rectangle, and shrinking the boundary afterwards ensures no cell is written twice. The re-checks before the bottom and left passes prevent double-writing when the remaining region is a single row or column.
Complexity
- Time —
O(n²) - Space —
O(n²) for the output
Pitfalls
- Skipping the mid-loop re-checks writes the centre row twice on odd
n. - The same boundary loop reads an arbitrary
m × nmatrix in spiral order — it is the general Spiral Matrix technique.
Reference solution
Python
def generateMatrix(n: int):
m = [[0] * n for _ in range(n)]
top, bottom, left, right = 0, n - 1, 0, n - 1
v = 1
while top <= bottom and left <= right:
for c in range(left, right + 1):
m[top][c] = v
v += 1
top += 1
for r in range(top, bottom + 1):
m[r][right] = v
v += 1
right -= 1
if top <= bottom:
for c in range(right, left - 1, -1):
m[bottom][c] = v
v += 1
bottom -= 1
if left <= right:
for r in range(bottom, top - 1, -1):
m[r][left] = v
v += 1
left += 1
return mJava
public static int[][] generateMatrix(int n) {
int[][] m = new int[n][n];
int top = 0, bottom = n - 1, left = 0, right = n - 1, v = 1;
while (top <= bottom && left <= right) {
for (int c = left; c <= right; c++) m[top][c] = v++;
top++;
for (int r = top; r <= bottom; r++) m[r][right] = v++;
right--;
if (top <= bottom) {
for (int c = right; c >= left; c--) m[bottom][c] = v++;
bottom--;
}
if (left <= right) {
for (int r = bottom; r >= top; r--) m[r][left] = v++;
left++;
}
}
return m;
}C++
vector<vector<int>> generateMatrix(int n) {
vector<vector<int>> m(n, vector<int>(n, 0));
int top = 0, bottom = n - 1, left = 0, right = n - 1, v = 1;
while (top <= bottom && left <= right) {
for (int c = left; c <= right; c++) m[top][c] = v++;
top++;
for (int r = top; r <= bottom; r++) m[r][right] = v++;
right--;
if (top <= bottom) {
for (int c = right; c >= left; c--) m[bottom][c] = v++;
bottom--;
}
if (left <= right) {
for (int r = bottom; r >= top; r--) m[r][left] = v++;
left++;
}
}
return m;
}JavaScript
var generateMatrix = function(n) {
const m = [];
for (let i = 0; i < n; i++) m.push(new Array(n).fill(0));
let top = 0, bottom = n - 1, left = 0, right = n - 1, v = 1;
while (top <= bottom && left <= right) {
for (let c = left; c <= right; c++) m[top][c] = v++;
top++;
for (let r = top; r <= bottom; r++) m[r][right] = v++;
right--;
if (top <= bottom) {
for (let c = right; c >= left; c--) m[bottom][c] = v++;
bottom--;
}
if (left <= right) {
for (let r = bottom; r >= top; r--) m[r][left] = v++;
left++;
}
}
return m;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Matrix and Grid Traversal