# LeetCode Solution, Medium, 59. Spiral Matrix II

# [59. Spiral Matrix II](https://leetcode.com/problems/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:**

![spiraln.jpeg](https://cdn.hashnode.com/res/hashnode/image/upload/v1649815263865/AMX1R-Ydo.jpeg)

    Input: n = 3
    Output: [[1,2,3],[8,9,4],[7,6,5]]

**Example 2:**

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

**Constraints:**

- `1 <= n <= 20`

### 題目翻譯

題目的需求很簡單就是會給一個整數參數 `n`，然後從數字 1 開始從外而內做順時針的螺旋排列。

## 解法解析

這題的解法有以下幾種方式：
1. 依照題目所說的從外而內的螺旋排列
2. 由內而外的排序，可以參考[討論區](https://leetcode.com/problems/spiral-matrix-ii/discuss/22282/4-9-lines-Python-solutions)的部分

其實主要就是判斷這個邊界索引的邏輯，有幾種方式：
1. 用四個變數紀錄四個方向的索引，如 Go 的第二個範例
2. 直接用計算的方式處理，優化的方式是使用取模。如 JavaScript 和 Python 的第二個範例

### 解法範例

#### Go

##### Traverse Layer

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

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

```javascript
/**
 * @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

```javascript
/**
 * @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

```kotlin
```

#### PHP

```php
```

#### Python

##### Traverse Layer

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

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

```rust
```

#### Swift

```swift
```