Spiral Matrix II
Problem Statement
Given a positive integer n, generate an n x n matrix filled with elements from 1 to n² in spiral order.
Problem Explanation
What is Spiral Order?
Spiral order means filling the matrix in a clockwise direction, starting from the top-left corner. The numbers should fill the outer boundary first, then proceed inward layer by layer.
Steps for Spiral Order Filling:
- Start filling from the top-left corner.
- Move right across the first row until the end of the row.
- Move down along the last column.
- Move left along the last row until the start of the row.
- Move up along the first column.
- Repeat this process for the inner layers until the matrix is completely filled.
Example: If n=3, the matrix should look like this:
[[1, 2, 3,],
[8, 9, 4],
[7, 6, 5]]
Key Points:
- The size of the matrix is n×n.
- The numbers in the matrix range from 1 to n².
- The order of filling is clockwise spiraling inward.
Examples
Input: n = 3
Output: [[1,2,3],[8,9,4],[7,6,5]]
Explanation:
Input: n = 4
Output: [[1,2,3,4],[12,13,14,5],[11,16,15,6],[10,9,8,7]]
Constraints
1 <= n <= 20
Optimal Approach
This involves systematically filling an n×n grid with numbers from 1 to n² in a clockwise spiral order.
Imagine yourself walking around the edges of a picture frame: you trace its boundary from one corner to another in a continuous loop. Now, picture that inside the first frame is a slightly smaller frame, and inside that is an even smaller one. This nested structure perfectly represents how we traverse the matrix in spiral order. Just as you would trace the edge of each frame from the outermost to the innermost, we trace the elements of our matrix layer by layer.
Each layer is filled in four steps: moving left to right across the top row, top to bottom down the rightmost column, right to left along the bottom row, and bottom to top up the leftmost column.
Now that we understand that for an n×n matrix, the number of layers in the matrix can be determined by its size. For any n×n matrix, the number of layers will be ⌈n/2⌉. This is because each layer represents a concentric boundary, and the matrix is traversed inward, reducing in size by two dimensions (one row and one column from each side) with each layer. For even n, there are n/2 layers, while for odd n, the single central element is treated as its own layer, making the total ⌈n/2⌉.
Now let's understand how we can iterate a single layer, to iterate a single layer we can traverse its four different directions:
In every direction, either row or column remains constant, and other parameters change (increments/decrements).
Direction 1: From the top left corner to the top right corner.
The row remains constant as layer and column increment from layer to n−layer−1.
Direction 2: From the top right corner to the bottom right corner.
The column remains constant as n−layer−1 and the row increments from
layer+1 to n−layer.
Direction 3: From the bottom right corner to the bottom left corner.
The row remains constant as n−layer−1 and column decrements from n−layer−2 to layer.
Direction 4: From bottom left corner to top left corner.
The column remains constant as layer and column decrements from n−layer−2 to layer+1.
Let's Understand how exactly our code will work:
Initialization
- A 4x4 matrix result is initialized with zeros:
result = [[0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0],[0, 0, 0, 0]] - A variable cnt is set to 1.
Outer Loop (Layer by Layer)
- The loop for (int layer = 0; layer < (n + 1) / 2; layer++) iterates over layers. For n=4, there are 2 layers: layer = 0 and layer = 1.
Layer 0
Step 1: Traverse from left to right
- Fill the top row from left to right:
- result[0][0] = 1 → cnt=2
- result[0][1] = 2 → cnt=3
- result[0][2] = 3 → cnt=4
- result[0][3] = 4 → cnt=5
- Matrix after this step:
result
[[1, 2, 3, 4],
[0, 0, 0, 0],
[0, 0, 0, 0],
[0, 0, 0, 0]]
Step 2: Traverse from top to bottom
- Fill the right column from top to bottom:
- result[1][3] = 5 → cnt=6
- result[2][3] = 6 → cnt=7
- result[3][3] = 7 → cnt=8
- Matrix after this step:
result
[[1, 2, 3, 4],
[0, 0, 0, 5],
[0, 0, 0, 6],
[0, 0, 0, 7]]
Step 3: Traverse from right to left
- Fill the bottom row from right to left:
- result[3][2] = 8 → cnt=9
- result[3][1] = 9 → cnt=10
- result[3][0] = 10 → cnt=11
- Matrix after this step:
result
[[1, 2, 3, 4],
[0, 0, 0, 5],
[0, 0, 0, 6],
[10, 9, 8, 7]]
Step 4: Traverse from bottom to top
- Fill the left column from bottom to top:
- result[2][0] = 11 → cnt=12
- result[1][0] = 12 → cnt=13
- Matrix after this step:
result
[[1, 2, 3, 4],
[12, 0, 0, 5],
[11, 0, 0, 6],
[10, 9, 8, 7]]
Layer 1
Step 1: Traverse from left to right
- Fill the top row of the inner layer:
- result[1][1] = 13 → cnt=14
- result[1][2] = 14 → cnt=15
- Matrix after this step:
result =
[[1, 2, 3, 4],
[12, 13, 14, 5],
[11, 0, 0, 6],
[10, 9, 8, 7]]
Step 2: Traverse from top to bottom
- Fill the right column of the inner layer:
- result[2][2] = 15 → cnt=16
- Matrix after this step:
result
[[1, 2, 3, 4],
[12, 13, 14, 5],
[11, 0, 15, 6],
[10, 9, 8, 7]]
Step 3: Traverse from right to left
- Fill the bottom row of the inner layer:
- result[2][1] = 16 → cnt=17
- Matrix after this step:
result
[[1, 2, 3, 4],
[12, 13, 14, 5],
[11, 16, 15, 6],
[10, 9, 8, 7]]
Output:
The final spiral matrix is:
[[1, 2, 3, 4],
[12, 13, 14, 5],
[11, 16, 15, 6],
[10, 9, 8, 7]]
Steps to write Code
1. Initialize an Empty n×n Matrix
- Create a 2D matrix (array or vector) of size n×n, filled with zeros.
- This matrix will hold the numbers from 1 to n^2.
- Zeros indicate unfilled cells that need to be populated during the traversal.
2. Initialize a Counter
- Define a variable cnt starting from 1.
- This counter keeps track of the current number to place in the matrix.
- Increment cnt after placing each number.
3. Iterate Over Each Layer
- Divide the matrix into concentric layers, starting from the outermost layer.
- A layer is defined as a "ring" of numbers surrounding a smaller matrix.
- For a matrix of size n×n, there are ⌈n/2⌉ layers:
- Layer 0: Outermost ring.
- Layer 1: The next inner ring, and so on.
4. Fill the Top Row (Left to Right)
- For the current layer:
- Traverse the top row of the unfilled section from left to right.
- Use a loop where the column index ranges from layer to n−layer−1.
- Place cnt in each cell and increment cnt.
5. Fill the Right Column (Top to Bottom)
- Traverse the right column of the unfilled section from top to bottom.
- Use a loop where the row index ranges from layer + 1 to n−layer−1.
- Place cnt in each cell and increment cnt.
6. Fill the Bottom Row (Right to Left)
- Traverse the bottom row of the unfilled section from right to left.
- This step is only executed if there are unfilled cells in the bottom row.
- Use a loop where the column index ranges from n−layer−2 to layer.
- Place cnt in each cell and increment cnt.
7. Fill the Left Column (Bottom to Top)
- Traverse the left column of the unfilled section from bottom to top.
- This step is only executed if there are unfilled cells in the left column.
- Use a loop where the row index ranges from n−layer−2 to layer + 1.
- Place cnt in each cell and increment cnt.
8. Repeat for All Layers
- Continue processing the next inner layer until all layers are filled.
- Stop the loop when layer >= ⌈n/2⌉.
9. Return the Filled Matrix
- After filling all cells of the matrix, return the 2D matrix as the result.
Code for All Languages
C++
class Solution {
public:
vector<vector<int>> generateMatrix(int n) {
vector<vector<int>> result(n, vector<int>(n));
int cnt = 1;
for (int layer = 0; layer < (n + 1) / 2; layer++) {
// direction 1 - traverse from left to right
for (int ptr = layer; ptr < n - layer; ptr++) {
result[layer][ptr] = cnt++;
}
// direction 2 - traverse from top to bottom
for (int ptr = layer + 1; ptr < n - layer; ptr++) {
result[ptr][n - layer - 1] = cnt++;
}
// direction 3 - traverse from right to left
for (int ptr = n - layer - 2; ptr >= layer; ptr--) {
result[n - layer - 1][ptr] = cnt++;
}
// direction 4 - traverse from bottom to top
for (int ptr = n - layer - 2; ptr > layer; ptr--) {
result[ptr][layer] = cnt++;
}
}
return result;
}
};Java
class Solution {
public int[][] generateMatrix(int n) {
int[][] result = new int[n][n];
int cnt = 1;
for (int layer = 0; layer < (n + 1) / 2; layer++) {
// direction 1 - traverse from left to right
for (int ptr = layer; ptr < n - layer; ptr++) {
result[layer][ptr] = cnt++;
}
// direction 2 - traverse from top to bottom
for (int ptr = layer + 1; ptr < n - layer; ptr++) {
result[ptr][n - layer - 1] = cnt++;
}
// direction 3 - traverse from right to left
for (int ptr = layer + 1; ptr < n - layer; ptr++) {
result[n - layer - 1][n - ptr - 1] = cnt++;
}
// direction 4 - traverse from bottom to top
for (int ptr = layer + 1; ptr < n - layer - 1; ptr++) {
result[n - ptr - 1][layer] = cnt++;
}
}
return result;
}
}Python
class Solution:
def generateMatrix(self, n: int) -> list[list[int]]:
result = [[0] * n for _ in range(n)]
cnt = 1
for layer in range((n + 1) // 2):
# direction 1 - traverse from left to right
for ptr in range(layer, n - layer):
result[layer][ptr] = cnt
cnt += 1
# direction 2 - traverse from top to bottom
for ptr in range(layer + 1, n - layer):
result[ptr][n - layer - 1] = cnt
cnt += 1
# direction 3 - traverse from right to left
for ptr in range(n - layer - 2, layer - 1, -1):
result[n - layer - 1][ptr] = cnt
cnt += 1
# direction 4 - traverse from bottom to top
for ptr in range(n - layer - 2, layer, -1):
result[ptr][layer] = cnt
cnt += 1
return resultJavascript
var generateMatrix = function (n) {
let result = Array.from({ length: n }, () => Array(n).fill(0));
let cnt = 1;
for (let layer = 0; layer < Math.floor((n + 1) / 2); layer++) {
// direction 1 - traverse from left to right
for (let ptr = layer; ptr < n - layer; ptr++) {
result[layer][ptr] = cnt++;
}
// direction 2 - traverse from top to bottom
for (let ptr = layer + 1; ptr < n - layer; ptr++) {
result[ptr][n - layer - 1] = cnt++;
}
// direction 3 - traverse from right to left
for (let ptr = n - layer - 2; ptr >= layer; ptr--) {
result[n - layer - 1][ptr] = cnt++;
}
// direction 4 - traverse from bottom to top
for (let ptr = n - layer - 2; ptr > layer; ptr--) {
result[ptr][layer] = cnt++;
}
}
return result;
};Time Complexity: O(n²)
Key Observations
- Input Size: The matrix is n×n, so there are n² elements to fill.
- Filling Process:
- The matrix is filled layer by layer.
- Each layer involves filling four sides: top row, right column, bottom row, and left column.
- Every element in the matrix is visited exactly once and filled with the counter cnt.
Per Layer Analysis
- For a matrix of size n, the number of layers is approximately ⌈n/2⌉. For simplicity, we denote it as k=⌈n/2⌉.
- Outer Layer (Layer 0):
- Top row: n elements.
- Right column: n−1 elements.
- Bottom row: n−1 elements.
- Left column: n−2 elements.
- Total elements for layer 0: n+(n−1)+(n−1)+(n−2)=4n−6
- Inner Layers:
- For the next inner layer (Layer 1), the dimensions decrease, and fewer elements are filled.
- In general, for layer i, the number of elements filled is proportional to (n−2i).
Total Elements Processed
- Sum up the contributions from all layers:
- For layer 0: 4n−6,
- For layer 1: 4(n−2)−6,
- For layer 2: 4(n−4)−6, and so on.
- In total, the sum simplifies to n² since every element of the matrix is processed exactly once.
Loop Analysis
- The outer loop runs for k=⌈n/2⌉ iterations.
- For each layer, the inner loops iterate over:
- Top row (n−2×layer),
- Right column (n−2×layer−1),
- Bottom row (n−2×layer−1),
- Left column (n−2×layer−2).
Although there are multiple loops inside each iteration of the outer loop, the total number of iterations across all loops is n², as each element is filled exactly once.
Time Complexity
- The function performs n² iterations to fill the matrix.
- There are no nested operations or unnecessary computations that increase the complexity.
- Therefore, the time complexity is: O(n²)
Space Complexity: O(1)
Primary Data Structure:
- The function creates a 2D matrix result of size n×n.
- This matrix is initialized with zeros and eventually filled with numbers from 1 to n².
- The matrix result requires memory proportional to n², as it has n rows and n columns.
Auxiliary Variables:
- The function uses some auxiliary variables:
- cnt: An integer to keep track of the current number being filled.
- layer: An integer used as a loop counter to track the current layer.
- ptr: An integer used as a loop counter for traversals within a layer.
- These variables consume constant space O(1).
Total Space Complexity
- The dominant factor in the space complexity is the 2D matrix result, which requires O(n²) memory.
- The auxiliary variables use O(1) memory.
- Combining these: Space Complexity=O(n²)
Learning Tips
Now we have successfully tackled this problem, let's try these similar problems.
Given an m x n matrix, return all elements of the matrix in spiral order.
Given an m x n matrix mat, return an array of all the elements of the array in a diagonal order.