# 59. Spiral Matrix II

## 題目敘述

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]]
``````

Example 2:

``````Input: n = 1
Output: [[1]]
``````

Constraints:

• `1 <= n <= 20`

## 解法解析

1. 依照題目所說的從外而內的螺旋排列
2. 由內而外的排序，可以參考討論區的部分

1. 用四個變數紀錄四個方向的索引，如 Go 的第二個範例
2. 直接用計算的方式處理，優化的方式是使用取模。如 JavaScript 和 Python 的第二個範例

### 解法範例

#### Go

##### Traverse Layer
``````func generateMatrix(n int) [][]int {
result := make([][]int, n)
for i := range result {
result[i] = make([]int, n)
}
var cnt int = 1
for layer := 0; layer < (n+1)/2; layer++ {
for i := layer; i < n-layer; i++ {
result[layer][i] = cnt
cnt++
}
for i := layer + 1; i < n-layer; i++ {
result[i][n-layer-1] = cnt
cnt++
}
for i := n - layer - 2; i >= layer; i-- {
result[n-layer-1][i] = cnt
cnt++
}
for i := n - layer - 2; i > layer; i-- {
result[i][layer] = cnt
cnt++
}
}
return result
}
``````
##### Traverse Layer for 4 directino
``````func generateMatrix(n int) [][]int {
if n == 0 {
return [][]int{}
}

result := make([][]int, n)
for i := range result {
result[i] = make([]int, n)
}

var top, bottom, left, right int = 0, n - 1, 0, n - 1
var cnt, layerRange int = 1, n * n
for cnt <= layerRange {
for i := left; i <= right && cnt <= layerRange; i++ {
result[top][i] = cnt
cnt++
}
top++

for i := top; i <= bottom && cnt <= layerRange; i++ {
result[i][right] = cnt
cnt++
}
right--

for i := right; i >= left && cnt <= layerRange; i-- {
result[bottom][i] = cnt
cnt++
}
bottom--

for i := bottom; i >= top && cnt <= layerRange; i-- {
result[i][left] = cnt
cnt++
}
left++
}

return result
}
``````

#### JavaScript

##### Traverse Layer
``````/**
* @param {number} n
* @return {number[][]}
*/
var generateMatrix = function (n) {
const result = new Array(n).fill(0).map(() => new Array(n).fill(0));
let cnt = 1;
for (let layer = 0; layer < Math.floor((n + 1) / 2); layer++) {
for (let i = layer; i < n - layer; i++) {
result[layer][i] = cnt++;
}
for (let i = layer + 1; i < n - layer; i++) {
result[i][n - layer - 1] = cnt++;
}
for (let i = layer + 1; i < n - layer; i++) {
result[n - layer - 1][n - i - 1] = cnt++;
}
for (let i = layer + 1; i < n - layer - 1; i++) {
result[n - i - 1][layer] = cnt++;
}
}

return result;
};
``````
##### Optimized spiral traversal
``````/**
* @param {number} n
* @return {number[][]}
*/
var generateMatrix = function (n) {
const result = [...Array(n)].map(() => Array(n).fill(0));
const dir = [
[0, 1],
[1, 0],
[0, -1],
[-1, 0],
];

let row = 0,
col = 0,
d = 0,
cnt = 1;
while (cnt <= n * n) {
result[row][col] = cnt++;

let r = (row + dir[d][0]) % n;
let c = (col + dir[d][1]) % n;

if (result[r][c] !== 0) {
d = (d + 1) % 4;
}

row += dir[d][0];
col += dir[d][1];
}

return result;
};
``````

#### Kotlin

``````
``````

#### PHP

``````
``````

#### Python

##### Traverse Layer
``````class Solution:
def generateMatrix(self, n: int) -> List[List[int]]:
result = [[0 for _ in range(n)] for _ in range(n)]
cnt = 1
for layer in range((n + 1) // 2):
# direction 1 - traverse from left to right
for i in range(layer, n - layer):
result[layer][i] = cnt
cnt += 1
# direction 2 - traverse from top to bottom
for i in range(layer + 1, n - layer):
result[i][n - layer - 1] = cnt
cnt += 1
# direction 3 - traverse from right to left
for i in range(layer + 1, n - layer):
result[n - layer - 1][n - i - 1] = cnt
cnt += 1
# direction 4 - traverse from bottom to top
for i in range(layer + 1, n - layer - 1):
result[n - i - 1][layer] = cnt
cnt += 1
return result
``````
##### Optimized spiral traversal
``````class Solution:
def generateMatrix(self, n: int) -> List[List[int]]:
result = [[0 for _ in range(n)] for _ in range(n)]
# right, down, left, up
dr = [[0, 1], [1, 0], [0, -1], [-1, 0]]
row, col, d, cnt = 0, 0, 0, 1

while cnt <= n * n:
result[row][col] = cnt

r = (row + dr[d][0]) % n
c = (col + dr[d][1]) % n

if result[r][c] != 0:
d = (d + 1) % 4

row += dr[d][0]
col += dr[d][1]
cnt += 1

return result
``````

#### Rust

``````
``````

#### Swift

``````
``````