#59
Spiral Matrix II
Medium Shrinking boundaries
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Build an n × n matrix filled with 1 to n² in clockwise spiral order.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: fill 1..n² in spiral order.
Why this works: the same four shrinking walls, writing a counter instead of reading.
Example: n = 3
1 2 38 9 47 6 5
✦Hints open one at a time
Same four boundaries as Spiral Matrix, but write instead of read.
A counter tells you which number to write next.
↗Approach
Fill the top row, right column, bottom row and left column, shrinking the boundaries each time, until the counter passes n².
</>Solution (Java)
class Solution {
public int[][] generateMatrix(int n) {
int[][] m = new int[n][n];
int top = 0, bottom = n - 1, left = 0, right = n - 1, k = 1;
while (k <= n * n) {
for (int c = left; c <= right; c++) m[top][c] = k++;
top++;
for (int r = top; r <= bottom; r++) m[r][right] = k++;
right--;
for (int c = right; c >= left; c--) m[bottom][c] = k++;
bottom--;
for (int r = bottom; r >= top; r--) m[r][left] = k++;
left++;
}
return m;
}
}!Common mistake
Off-by-one on the boundaries leading to overwriting cells already filled.
Complexity
- Time: O(n²).
- Space: O(1) besides the output.
Topic: 2D Arrays & Matrix
🎬 Episode 14: video coming soon