# Spiral Matrix II
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/spiral-matrix-ii)
Canonical: https://scaleengineer.com/dsa/problems/spiral-matrix-ii
**Data structures:** Array, Matrix
**Companies:** [Adobe](https://scaleengineer.com/companies/adobe), [Amazon](https://scaleengineer.com/companies/amazon), [Bloomberg](https://scaleengineer.com/companies/bloomberg), [Google](https://scaleengineer.com/companies/google), [Meta](https://scaleengineer.com/companies/meta), [Microsoft](https://scaleengineer.com/companies/microsoft), [Roblox](https://scaleengineer.com/companies/roblox), [TikTok](https://scaleengineer.com/companies/tiktok), [Uber](https://scaleengineer.com/companies/uber), [Zoho](https://scaleengineer.com/companies/zoho)
---
## Problem
Given a positive integer `n`, generate an `n x n` `matrix` filled with elements from `1` to `n2` in spiral order.

**Example 1:**

![](https://assets.glich.co/dsa/spiral-matrix-ii/image0.jpg) 

**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
## Simulation with Direction Control
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.
**Time:** O(n^2) · **Space:** O(1) (excluding the output matrix)
**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.
### Explanation
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.

```java
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;
    }
}
```
### Algorithm
1. Initialize an `n x n` matrix, `matrix`, with zeros.
2. Initialize `row = 0`, `col = 0`.
3. Define an array of directions `dirs = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}` for Right, Down, Left, Up.
4. Initialize a direction index `dirIndex = 0`.
5. Loop with a counter `val` from `1` to `n*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. Update `row` and `col` for the next iteration based on the current `dirIndex`.
6. Return the filled `matrix`.

## Layer-by-Layer Construction
This is a highly structured and robust approach where the matrix is filled in concentric layers, from the outside in. We use four pointers to define the boundaries of the current layer: `top`, `bottom`, `left`, and `right`. In each iteration, we fill the top row, right column, bottom row, and left column of the current layer, and then shrink the boundaries to move to the next inner layer. This continues until the boundaries cross each other.
**Time:** O(n^2) · **Space:** O(1) (excluding the output matrix)
**Pros:** Very structured and less prone to off-by-one errors compared to direction-based simulation.; The logic elegantly handles both even and odd `n` values.; Optimal time and space complexity.
**Cons:** The code can be slightly more verbose due to the four separate for-loops inside the main while-loop.
### Explanation
We start with the boundaries representing the entire matrix: `top = 0`, `bottom = n - 1`, `left = 0`, `right = n - 1`. A counter `num` starts at 1.

The process is contained within a `while` loop that runs as long as `left <= right` and `top <= bottom`. Inside the loop, we perform four distinct steps to fill one layer:
1.  **Fill Top Row**: Traverse from `left` to `right` and fill `matrix[top][i]`. Then, move the `top` boundary down (`top++`).
2.  **Fill Right Column**: Traverse from `top` to `bottom` and fill `matrix[i][right]`. Then, move the `right` boundary left (`right--`).
3.  **Fill Bottom Row**: Traverse from `right` to `left` and fill `matrix[bottom][i]`. Then, move the `bottom` boundary up (`bottom--`).
4.  **Fill Left Column**: Traverse from `bottom` to `top` and fill `matrix[i][left]`. Then, move the `left` boundary right (`left++`).

Conditional checks (`if (top <= bottom)` and `if (left <= right)`) are needed before filling the bottom row and left column to correctly handle matrices where `n` is odd, which results in a single central element or a single row/column in the center.

```java
class Solution {
    public int[][] generateMatrix(int n) {
        int[][] matrix = new int[n][n];
        if (n == 0) {
            return matrix;
        }
        
        int top = 0, bottom = n - 1;
        int left = 0, right = n - 1;
        int num = 1;
        
        while (top <= bottom && left <= right) {
            // Traverse Right (fill top row)
            for (int i = left; i <= right; i++) {
                matrix[top][i] = num++;
            }
            top++;
            
            // Traverse Down (fill right column)
            for (int i = top; i <= bottom; i++) {
                matrix[i][right] = num++;
            }
            right--;
            
            // Traverse Left (fill bottom row)
            if (top <= bottom) { // Check if there's still a valid row to fill
                for (int i = right; i >= left; i--) {
                    matrix[bottom][i] = num++;
                }
                bottom--;
            }
            
            // Traverse Up (fill left column)
            if (left <= right) { // Check if there's still a valid column to fill
                for (int i = bottom; i >= top; i--) {
                    matrix[i][left] = num++;
                }
                left++;
            }
        }
        
        return matrix;
    }
}
```
### Algorithm
1. Create an `n x n` matrix, `matrix`.
2. Initialize a counter `num = 1`.
3. Initialize four boundary pointers: `top = 0`, `bottom = n - 1`, `left = 0`, `right = n - 1`.
4. Loop as long as `top <= bottom` and `left <= right`:
    a. **Fill top row**: Iterate from `left` to `right`, setting `matrix[top][i] = num++`.
    b. Increment `top`.
    c. **Fill right column**: Iterate from `top` to `bottom`, setting `matrix[i][right] = num++`.
    d. Decrement `right`.
    e. **Fill bottom row**: If `top <= bottom`, iterate from `right` down to `left`, setting `matrix[bottom][i] = num++`.
    f. Decrement `bottom`.
    g. **Fill left column**: If `left <= right`, iterate from `bottom` down to `top`, setting `matrix[i][left] = num++`.
    h. Increment `left`.
5. Return the filled `matrix`.

# Solutions
### Java

```java
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;
  }
}

```

### JavaScript

```javascript
/** * @param {number} n * @return {number[][]} */ var generateMatrix =
  function (n) {
    const ans = new Array(n).fill(0).map(() => new Array(n).fill(0));
    let [i, j, k] = [0, 0, 0];
    const dirs = [
      [0, 1],
      [1, 0],
      [0, -1],
      [-1, 0],
    ];
    for (let v = 1; v <= n * n; ++v) {
      ans[i][j] = v;
      let [x, y] = [i + dirs[k][0], j + dirs[k][1]];
      if (x < 0 || y < 0 || x >= n || y >= n || ans[x][y] > 0) {
        k = (k + 1) % 4;
        [x, y] = [i + dirs[k][0], j + dirs[k][1]];
      }
      [i, j] = [x, y];
    }
    return ans;
  };

```

### CPP

```cpp
class Solution {
public:
  const int dirs[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
  vector<vector<int>> generateMatrix(int n) {
    vector<vector<int>> ans(n, vector<int>(n));
    int i = 0, j = 0, k = 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]) {
        k = (k + 1) % 4;
        x = i + dirs[k][0], y = j + dirs[k][1];
      }
      i = x, j = y;
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def generateMatrix(self, n: int) -> List[List[int]]: ans = [[0] * n for _ in range(n)] dirs = ((0, 1), (1, 0), (0, - 1), (- 1, 0)) i = j = k = 0 for v in range(1, n * n + 1): ans[i][j] = v x, y = i + dirs[k][0], j + dirs[k][1] if x < 0 or y < 0 or x >= n or y >= n or ans[x][y]: k = (k + 1) % 4 x, y = i + dirs[k][0], j + dirs[k][1] i, j = x, y return ans

```