Given a positive integer n, generate an n x n matrix filled with elements from 1 to n2 in spiral order.
Example 1:
Input: n = 3 Output: [[1,2,3],[8,9,4],[7,6,5]]
Example 2:
Input: n = 1 Output: [[1]]
Constraints:
1 <= n <= 20In #59 Spiral Matrix II, the goal is to generate an n x n matrix filled with numbers from 1 to n² arranged in a spiral order. The most intuitive way to approach this problem is through simulation using boundary pointers.
Maintain four boundaries: top, bottom, left, and right. These pointers represent the current layer of the matrix that still needs to be filled. Start filling numbers from left to right across the top row, then top to bottom along the right column, followed by right to left along the bottom row, and finally bottom to top along the left column.
After completing each direction, update the corresponding boundary inward. Continue this process until all cells are filled. Since every cell in the matrix is visited exactly once, the algorithm runs efficiently. This approach relies on careful boundary management rather than complex data structures.
The overall time complexity is O(n²) because each matrix cell is filled once, while the additional space complexity is O(1) apart from the output matrix.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Boundary Simulation (Spiral Traversal) | O(n²) | O(1) extra space |
NeetCode
This approach involves iteratively filling the matrix in a spiral pattern while maintaining boundary limits. We initialize four boundaries: top, bottom, left, and right. Starting with top as 0 and so on, we fill the elements from 1 to n2 within these boundaries:
This process repeats until all numbers are placed in the matrix.
Time Complexity: O(n^2), as we iterate through every cell of the matrix.
Space Complexity: O(1) for in-place modification, excluding the space required for the output matrix.
1#include <stdio.h>
2#include <stdlib.h>
3
4int** generateMatrix(int n, int* returnSize,
The function generateMatrix initializes a 2D array of size n x n and fills it in spiral order using boundary markers. The loop continues until all elements are filled, adjusting the boundaries as needed after each direction traversal.
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, spiral traversal and matrix simulation problems frequently appear in technical interviews at companies like Amazon, Google, and Meta. They test a candidate's ability to manage boundaries and implement clean iteration logic.
The time complexity is O(n²) because the algorithm fills each cell of the n x n matrix exactly once. No cell is revisited, making the approach efficient for the problem size.
The optimal approach uses boundary-based simulation. By maintaining top, bottom, left, and right pointers, you can fill the matrix layer by layer in spiral order until all numbers from 1 to n² are placed.
A simple 2D array (matrix) is sufficient for this problem. The algorithm mainly relies on pointer manipulation and controlled traversal rather than advanced data structures.