Log inSign up
mediumLeetCodeNot Started

Spiral Matrix II

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Arrays
Solve on LeetCode
Lesson

Problem Statement

Given a positive integer n, generate an n x n matrix filled with elements from 1 to n^2 in spiral order.

Example 1:

Input: n = 3
Output: [[1,2,3],[8,9,4],[7,6,5]]
Explanation: Numbers 1 through 9 are placed clockwise along the perimeter and then inward to fill the 3x3 grid.

Example 2:

Input: n = 1
Output: [[1]]
Explanation: Single cell matrix containing just 1.

Constraints:

  • 1 <= n <= 20

Prerequisites

Before attempting this problem, you should be comfortable with:

  • 2D array allocation and indexing in chosen programming language
  • Boundary manipulation and two-pointer shrink patterns

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Master the 4-pointer boundary contraction paradigm (top, bottom, left, right).
  • Prevent duplicate index writes and boundary overshoot in spiral traversals.
  • Generate 2D arrays in-place with strictly O(1) auxiliary memory.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Generating or reading a 2D matrix in clockwise spiral perimeter order.
  • Fixed boundary shrinking constraints across 4 directions.
  • Filling sequential values 1 to N2 directly into output structure.

Algorithmic Decision Tree:

  • Use 4-boundary pointers (top, bottom, left, right) to define the current active bounding box.
  • Execute the 4 sequential passes: (1) Left->Right, (2) Top->Bottom, (3) Right->Left, (4) Bottom->Top, shrinking the corresponding boundary after each pass.

Connected Patterns:

Spiral Matrix (LeetCode 54)Rotate Image (LeetCode 48)Diagonal Traverse (LeetCode 498)

1. Direction Vector & Turn-on-Collision Simulation

Intuition

Mimic a physical pen drawing spiral lines that turns right whenever an obstacle or boundary is encountered.

Algorithm

  1. Step 1: Allocate matrix of size n x n filled with 0s.
  2. Step 2: Define directions: dirs = [[0,1], [1,0], [0,-1], [-1,0]]. Initialize dirIdx = 0, r = 0, c = 0.
  3. Step 3: Loop num from 1 to n*n, setting matrix[r][c] = num.
  4. Step 4: Calculate candidate next position (nr, nc) = (r + dirs[dirIdx][0], c + dirs[dirIdx][1]).
  5. Step 5: If (nr, nc) is out of bounds or matrix[nr][nc] != 0, rotate direction: dirIdx = (dirIdx + 1) % 4.
  6. Step 6: Update r = r + dirs[dirIdx][0] and c = c + dirs[dirIdx][1].

Direction Vector Simulation Trace

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [1, 2, 3, 4, 5, 6, 7, 8, 9]
Current operationSTEP 1 OF 6
Allocate 3x3 matrix initialized to 0
Visual state
Values and pointers at this exact step
pointers
S
1
0
0
0
↑ val=1
1
2
Variables at this step
r
0
c
0
val
1
dir
Right
Check / comparison
grid[0][0] == 0
Decision / next transition
Write grid[0][0] = 1, advance right.
Why this step matters

Allocate 3x3 matrix initialized to 0. Position (r=0, c=0), direction dr=0, dc=1 (Right).

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4class Solution {
5public:
6 std::vector<std::vector<int>> generateMatrix(int n) {
7 std::vector<std::vector<int>> matrix(n, std::vector<int>(n, 0));
8 int dirs[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}; // R, D, L, U
9 int d = 0, r = 0, c = 0;
10
11 for (int num = 1; num <= n * n; ++num) {
12 matrix[r][c] = num;
13 int nr = r + dirs[d][0];
14 int nc = c + dirs[d][1];
15
16 if (nr < 0 || nr >= n || nc < 0 || nc >= n || matrix[nr][nc] != 0) {
17 d = (d + 1) % 4; // Turn clockwise
18 }
19 r += dirs[d][0];
20 c += dirs[d][1];
21 }
22
23 return matrix;
24 }
25};
26
27int main() {
28 Solution solver;
29 auto res = solver.generateMatrix(3);
30 for (const auto& row : res) {
31 for (int x : row) std::cout << x << " ";
32 std::cout << "
33";
34 }
35 return 0;
36}

Time & Space Complexity

  • Time complexity: O(N^2) — Time complexity for Direction Vector & Turn-on-Collision Simulation.
  • Space complexity: O(1) — Space complexity for Direction Vector & Turn-on-Collision Simulation.

Why Brute Force Doesn't Scale:

For N = 105, quadratic O(N2) approaches require ~1010 operations, exceeding the standard 1-second CPU budget.

The optimal approach processes N elements in a single or logarithmic pass, completing in under 10ms with minimal memory footprint.

2. Layer-by-Layer Concentric Ring Filling

Intuition

An n x n matrix consists of ceil(n/2) concentric square layers. Filling layer k independently reduces edge condition errors.

Algorithm

  1. Step 1: Iterate layer index from 0 to (n - 1) / 2.
  2. Step 2: For current layer, top-left is (layer, layer) and bottom-right is (n - 1 - layer, n - 1 - layer).
  3. Step 3: Fill top edge, right edge, bottom edge, and left edge.
  4. Step 4: Special case: if layer reaches the center cell for odd n, assign the final number directly.

Layer-by-Layer Concentric Ring Trace

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [1, 2, 3, 4, 5, 6, 7, 8, 9]
Current operationSTEP 1 OF 6
Layer 0 Top row: write values 1, 2, 3 into row 0 from col 0 to 2
Visual state
Values and pointers at this exact step
pointers
S
1
2
3
0
1
2
↑ top side
Variables at this step
layer
0
side
top
val
3
Check / comparison
c from 0 to 2
Decision / next transition
grid[0][0]=1, grid[0][1]=2, grid[0][2]=3.
Why this step matters

Layer 0 Top row: write values 1, 2, 3 into row 0 from col 0 to 2.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4class Solution {
5public:
6 std::vector<std::vector<int>> generateMatrix(int n) {
7 std::vector<std::vector<int>> matrix(n, std::vector<int>(n));
8 int num = 1;
9 for (int layer = 0; layer < (n + 1) / 2; ++layer) {
10 int last = n - 1 - layer;
11 if (layer == last) {
12 matrix[layer][layer] = num++;
13 break;
14 }
15 for (int c = layer; c < last; ++c) matrix[layer][c] = num++;
16 for (int r = layer; r < last; ++r) matrix[r][last] = num++;
17 for (int c = last; c > layer; --c) matrix[last][c] = num++;
18 for (int r = last; r > layer; --r) matrix[r][layer] = num++;
19 }
20 return matrix;
21 }
22};
23
24int main() {
25 Solution solver;
26 auto res = solver.generateMatrix(3);
27 for (const auto& row : res) {
28 for (int x : row) std::cout << x << " ";
29 std::cout << "
30";
31 }
32 return 0;
33}

Time & Space Complexity

  • Time complexity: O(N^2) — Time complexity for Layer-by-Layer Concentric Ring Filling.
  • Space complexity: O(1) — Space complexity for Layer-by-Layer Concentric Ring Filling.

3. 4-Boundary Shrinking Pointers (Standard Optimal)

Intuition

By incrementing/decrementing boundaries after each side is filled, the loop naturally contracts inwards without needing index arithmetic or special center case handling.

Algorithm

  1. Step 1: Initialize matrix of size n x n, num = 1.
  2. Step 2: Initialize top = 0, bottom = n - 1, left = 0, right = n - 1.
  3. Step 3: Loop while left <= right and top <= bottom.
  4. Step 4: Traverse left to right along row top: matrix[top][c] = num++, then top++.
  5. Step 5: Traverse top to bottom along col right: matrix[r][right] = num++, then right--.
  6. Step 6: Traverse right to left along row bottom: matrix[bottom][c] = num++, then bottom--.
  7. Step 7: Traverse bottom to top along col left: matrix[r][left] = num++, then left++.
  8. Step 8: Return filled matrix.

4-Boundary Shrinking Pointers Trace

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [1, 2, 3, 4, 5, 6, 7, 8, 9]
Current operationSTEP 1 OF 6
Initialize boundaries: top=0, bottom=2, left=0, right=2, num=1
Visual state
Values and pointers at this exact step
pointers
S
1
2
3
0
1
2
↑ top row
Variables at this step
top
1
bottom
2
left
0
right
2
num
4
Check / comparison
top <= bottom && left <= right
Decision / next transition
Traverse left to right along top row: write 1, 2, 3. Increment top to 1.
Why this step matters

Initialize boundaries: top=0, bottom=2, left=0, right=2, num=1.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4class Solution {
5public:
6 std::vector<std::vector<int>> generateMatrix(int n) {
7 std::vector<std::vector<int>> matrix(n, std::vector<int>(n));
8 int top = 0, bottom = n - 1;
9 int left = 0, right = n - 1;
10 int num = 1;
11
12 while (top <= bottom && left <= right) {
13 // 1. Traverse Left to Right across top boundary
14 for (int c = left; c <= right; ++c) {
15 matrix[top][c] = num++;
16 }
17 top++;
18
19 // 2. Traverse Top to Bottom across right boundary
20 for (int r = top; r <= bottom; ++r) {
21 matrix[r][right] = num++;
22 }
23 right--;
24
25 // 3. Traverse Right to Left across bottom boundary
26 if (top <= bottom) {
27 for (int c = right; c >= left; --c) {
28 matrix[bottom][c] = num++;
29 }
30 bottom--;
31 }
32
33 // 4. Traverse Bottom to Top across left boundary
34 if (left <= right) {
35 for (int r = bottom; r >= top; --r) {
36 matrix[r][left] = num++;
37 }
38 left++;
39 }
40 }
41
42 return matrix;
43 }
44};
45
46int main() {
47 Solution solver;
48 auto res3 = solver.generateMatrix(3);
49 std::cout << "3x3 Spiral Matrix:
50";
51 for (const auto& row : res3) {
52 for (int x : row) std::cout << x << " ";
53 std::cout << "
54";
55 }
56
57 auto res1 = solver.generateMatrix(1);
58 std::cout << "
591x1 Spiral Matrix:
60" << res1[0][0] << "
61";
62 return 0;
63}

Time & Space Complexity

  • Time complexity: O(N^2) — Time complexity for 4-Boundary Shrinking Pointers (Standard Optimal).
  • Space complexity: O(1) — Space complexity for 4-Boundary Shrinking Pointers (Standard Optimal).

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Brute Force — Direction Vector Turn SimulationO(N^2)O(1) extraSimulate a pen walking with direction vector [dr, dc], turning 90 degrees clockwise when hitting an edge or non-zero filled cell.Collision detection branch checks.
2.Better — Concentric Layer PeelingO(N^2)O(1) extraIterate through each concentric square ring layer from 0 to ceil(N/2).Layer boundary offset arithmetic.
3.Optimal — 4-Boundary Shrinking PointersOptimalO(N^2)O(1) extraMaintain top, bottom, left, right and shrink respective pointer after writing each edge.None; theoretical optimum.

Common Pitfalls & Crucial Edge Cases

Off-by-One Errors

Incorrect boundary indexing when adjusting pointers or array slices.

Integer Overflow

Using 32-bit signed integer types when accumulative operations exceed 231 - 1 in C++/Java.

Unnecessary Memory Allocation

Allocating large auxiliary arrays or objects inside inner loops causing GC overhead.

Failing to Reset Loop State

Not re-initializing state variables or counters between iterations or subproblems.

Crucial Edge Cases to Validate:

  • Edge Case — Input: `, Expected: ` —
  • Edge Case — Input: `, Expected: ` —
  • Edge Case — Input: `, Expected: ` —

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. State the difference clearly with Spiral Matrix I (generating values 1..N2 vs reading existing values).
  2. Explain the 4-pointer shrink invariant: each boundary handles exactly one edge per pass.
  3. Highlight why O(1) auxiliary space is achieved since the output matrix is the required return value.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.What is the optimal time and auxiliary space complexity for Spiral Matrix II?

2.Why is the brute force approach suboptimal for large inputs in Spiral Matrix II?

3.Which data structure or technique enables the optimal solution for Spiral Matrix II?

Back to DSA Sheet