Spiral Matrix II
MedPrompt
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 <= 20
Approaches
2 approaches with complexity analysis and trade-offs.
This approach simulates filling the matrix by 'walking' in a spiral path. We keep track of the current position (row, col) and the current direction of movement (right, down, left, up). We start at (0, 0) and move in one direction, filling numbers sequentially. When we hit a boundary or an already filled cell, we turn 90 degrees clockwise and continue. This process is repeated until all n*n cells are filled.
Algorithm
- Initialize an
n x nmatrix,matrix, with zeros. - Initialize
row = 0,col = 0. - Define an array of directions
dirs = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}for Right, Down, Left, Up. - Initialize a direction index
dirIndex = 0. - Loop with a counter
valfrom1ton*n: a. Place the current value:matrix[row][col] = val. b. Calculate the coordinates of the next cell in the current direction:nextRow,nextCol. c. Check if(nextRow, nextCol)is out of bounds or has already been filled (i.e.,matrix[nextRow][nextCol] != 0). d. If the next cell is invalid, update the direction:dirIndex = (dirIndex + 1) % 4. e. Updaterowandcolfor the next iteration based on the currentdirIndex. - Return the filled
matrix.
Walkthrough
We can implement this by maintaining the current coordinates (row, col) and a direction index. An array of directions, e.g., {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}, can represent the four movements (Right, Down, Left, Up).
The process starts at (0, 0) with the initial direction as Right. We loop from 1 to n*n, placing each number in the matrix. After placing a number, we check if the next step in the current direction is valid (i.e., within the matrix bounds and not already visited). If it's not valid, we update our direction to the next one in the sequence (e.g., from Right to Down). Then, we update our current (row, col) based on the (possibly new) direction to prepare for the next number.
class Solution { public int[][] generateMatrix(int n) { int[][] matrix = new int[n][n]; if (n == 0) { return matrix; } int row = 0, col = 0; // Directions: 0: Right, 1: Down, 2: Left, 3: Up int[][] dirs = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}; int dirIndex = 0; for (int val = 1; val <= n * n; val++) { matrix[row][col] = val; // Calculate the next potential position int nextRow = row + dirs[dirIndex][0]; int nextCol = col + dirs[dirIndex][1]; // Check if the next position is invalid (out of bounds or already filled) if (nextRow < 0 || nextRow >= n || nextCol < 0 || nextCol >= n || matrix[nextRow][nextCol] != 0) { // If invalid, change direction (turn 90 degrees clockwise) dirIndex = (dirIndex + 1) % 4; } // Update position for the next number to be placed // This update is skipped for the very last number to avoid out-of-bounds access. if (val < n * n) { row += dirs[dirIndex][0]; col += dirs[dirIndex][1]; } } return matrix; }}Complexity
Time
O(n^2)
Space
O(1) (excluding the output matrix)
Trade-offs
Pros
Directly simulates the spiral path, which is intuitive.
Optimal time and space complexity.
Cons
The logic for changing direction and updating the position requires careful handling to avoid off-by-one errors or out-of-bounds access, especially at the end of the traversal.
Solutions
Solution
class Solution {public int[][] generateMatrix(int n) { int[][] ans = new int[n][n]; int i = 0, j = 0, k = 0; int[][] dirs = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}; for (int v = 1; v <= n * n; ++v) { ans[i][j] = v; int x = i + dirs[k][0], y = j + dirs[k][1]; if (x < 0 || y < 0 || x >= n || y >= n || ans[x][y] > 0) { k = (k + 1) % 4; x = i + dirs[k][0]; y = j + dirs[k][1]; } i = x; j = y; } return ans; }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.