# Question

Formatted question description: https://leetcode.ca/all/59.html

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

# Algorithm

Given that the rectangle is a square, we use n / 2 to calculate the number of rings. If n is an odd number, the middle point is not counted in the number of rings, so it needs to be assigned separately in the end, or the problem of subscript conversion Is difficult.

# Code

• 
public class Spiral_Matrix_II {

// @note: compare: very similar to rotate image one, layer by layer, each layer: length-2
public class Solution_by_layer {
public int[][] generateMatrix(int n) {
if (n < 0) {
return null;
}

int[][] result = new int[n][n];

int xStart = 0;
int yStart = 0;
int num = 1;

while (n > 0) {
if (n == 1) { // if n is even, then no single center point
result[yStart][xStart] = num++;
break;
}

for (int i = 0; i < n - 1; i++) {
result[yStart][xStart + i] = num++;
}

for (int i = 0; i < n - 1; i++) {
result[yStart + i][xStart + n - 1] = num++;
}

for (int i = 0; i < n - 1; i++) {
result[yStart + n - 1][xStart + n - 1 - i] = num++;
}

for (int i = 0; i < n - 1; i++) {
result[yStart + n - 1 - i][xStart] = num++;
}

xStart++;
yStart++;
n = n - 2;
}

return result;
}
}

public class Solution {

public int[][] generateMatrix(int n) {

int[][] result = new int[n][n];

if (n <= 0) {
return result;
}

int i = 0, j = 0; // initiate row and column

int leftBoundary = 0, upBoundary = 1;
int rightBoundary = n - 1, downBoundary = n - 1; // marking boundary index

/*
direction: 1 is up, 2 is down, 3 is left, 4 is right
*/

// at beginning direction is right;
int direction = 4;

for (int num = 1; num <= n * n; num++) {

result[i][j] = num;

// switch case
if (direction == 1) { // move right

if (i == upBoundary) {
direction = 4;
j++;

upBoundary++;

} else {
i--;
}
}

else if (direction == 2) {

if (i == downBoundary) {
direction = 3;
j--;

// update boundary
downBoundary--;
} else {
i++;
}
}

else if (direction == 3) {

if (j == leftBoundary) {
direction = 1;
i--;

// update boundary
leftBoundary++;

} else {
j--;
}
}

else { // direction == 4

// check boundary
if (j == rightBoundary) {
direction = 2;
i++;

// row boundary is 1 less now
rightBoundary--;
} else {
j++;
}

}
}

return result;

}
}

}

############

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

• // OJ: https://leetcode.com/problems/spiral-matrix-ii/
// Time: O(N^2)
// Space: O(1) extra space
class Solution {
public:
vector<vector<int>> generateMatrix(int n) {
vector<vector<int>> ans(n, vector<int>(n));
for (int i = 0, d = 1; i < n / 2; ++i) {
int len = n - 2 * i - 1;
for (int j = 0; j < len; ++j) ans[i][i + j] = d++;
for (int j = 0; j < len; ++j) ans[i + j][n - i - 1] = d++;
for (int j = 0; j < len; ++j) ans[n - i - 1][n - i - j - 1] = d++;
for (int j = 0; j < len; ++j) ans[n - i - j - 1][i] = d++;
}
if (n % 2) ans[n / 2][n / 2] = n * n;
return ans;
}
};

• 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

############

class Solution(object):
def generateMatrix(self, n):
"""
:type n: int
:rtype: List[List[int]]
"""
ans = [[0] * n for _ in range(n)]
left, right, up, down = 0, n - 1, 0, n - 1
k = 1
while left <= right and up <= down:
for i in range(left, right + 1):
ans[up][i] = k
k += 1
up += 1
for i in range(up, down + 1):
ans[i][right] = k
k += 1
right -= 1
for i in reversed(range(left, right + 1)):
ans[down][i] = k
k += 1
down -= 1
for i in reversed(range(up, down + 1)):
ans[i][left] = k
k += 1
left += 1
return ans


• func generateMatrix(n int) [][]int {
ans := make([][]int, n)
for i := range ans {
ans[i] = make([]int, n)
}
dirs := [4][2]int{ {0, 1}, {1, 0}, {0, -1}, {-1, 0} }
var i, j, k int
for v := 1; v <= n*n; v++ {
ans[i][j] = v
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
}

• function generateMatrix(n: number): number[][] {
let ans = Array.from({ length: n }, v => new Array(n));
let dir = [
[0, 1],
[1, 0],
[0, -1],
[-1, 0],
];
let i = 0,
j = 0;
for (let cnt = 1, k = 0; cnt <= n * n; cnt++) {
ans[i][j] = cnt;
let x = i + dir[k][0],
y = j + dir[k][1];
if (x < 0 || x == n || y < 0 || y == n || ans[x][y]) {
k = (k + 1) % 4;
(x = i + dir[k][0]), (y = j + dir[k][1]);
}
(i = x), (j = y);
}
return ans;
}


• /**
* @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;
};


• impl Solution {
pub fn generate_matrix(n: i32) -> Vec<Vec<i32>> {
let n = n as usize;
let mut res = vec![vec![0; n]; n];
let mut num = 1;
for i in 0..n / 2 {
for j in i..n - i - 1 {
res[i][j] = num;
num += 1;
}
for j in i..n - i - 1 {
res[j][n - i - 1] = num;
num += 1;
}
for j in i..n - i - 1 {
res[n - i - 1][n - j - 1] = num;
num += 1;
}
for j in i..n - i - 1 {
res[n - j - 1][i] = num;
num += 1;
}
}
if n % 2 == 1 {
res[n >> 1][n >> 1] = num;
}
res
}
}