Spiral Matrix II Problem: Given a positive integer n
, generate an n x n
matrix
filled with elements from 1
to n2
in spiral order.
Input: n = 3 Output: [[1,2,3],[8,9,4],[7,6,5]]
Table of Contents
Spiral Matrix II Problem Solution
Problem Solution In Python
class Solution:
def generateMatrix(self, n: int) -> List[List[int]]:
matrix = []
total = n*n
for i in range(1,total+1):
matrix.append(i)
result = [[None]*n for _ in range(n)]
for d in range(n-1):
for i in range(d, n-d-1):
result[d][i]=matrix.pop(0)
for i in range(d, n-d-1):
result[i][n-d-1]=matrix.pop(0)
for i in range(n-d-1,d,-1):
result[n-d-1][i]=matrix.pop(0)
for i in range(n-d-1,d,-1):
result[i][d]=matrix.pop(0)
if n%2:
x= (n-1)//2
result[x][x]=matrix.pop()
return result
Problem Solution In Java
public int[][] generateMatrix(int n) {
int[][] directions = new int[][]{{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
int dirIndex = 0;
int x = 0, y = 0;
int[][] res = new int[n][n];
for (int i = 1; i <= n * n; i++) {
res[x][y] = i;
//System.out.println(Arrays.deepToString(res));
x = x + directions[dirIndex][0];
y = y + directions[dirIndex][1];
if (!isValid(x, y, res, n)) {
x = x - directions[dirIndex][0];
y = y - directions[dirIndex][1];
dirIndex = (dirIndex + 1) % 4;
x = x + directions[dirIndex][0];
y = y + directions[dirIndex][1];
}
}
return res;
}
private boolean isValid(int x, int y, int[][] res, int n) {
return (x >= 0 && x < n && y >= 0 && y < n && res[x][y] == 0);
}
Problem Solution In C++
vector<vector<int> > generateMatrix(int n) {
vector<vector<int> >matrix(n,vector<int>(n,0));
int r = n-1;
int c = n-1;
int cur = 1;
for(int i = 0;i<(n+1)/2;++i)
{
for(int j = i;j<=c-i;++j) matrix[i][j] = cur++;
for(int j = i+1;j<=r-i ;++j) matrix[j][c-i] = cur++;
for(int j = c-i-1;j>=i && r-i>i;--j) matrix[r-i][j] = cur++;
for(int j = r-i-1;j>i && c-i>i ;--j) matrix[j][i] = cur++;
}
return matrix;
}
Problem Solution In C
int** generateMatrix(int n, int* returnSize, int** returnColumnSizes){
int direction[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
*returnSize = n;
int** matrix = (int**) malloc(n * sizeof(int*));
*returnColumnSizes = (int*) malloc(n * sizeof(int));
int counter = 1;
for (int i = 0; i < n; i++) {
matrix[i] = (int*) malloc(n * sizeof(int));
(*returnColumnSizes)[i] = n;
}
for (int round = 0; round < (n + 1) / 2; round++){
int x = round, y = round;
matrix[x][y] = counter; /* This is for the case n is odd. */
for (int i = 0; i < 4; i++) {
for (int j = round; j < n - 1 - round; j++) {
matrix[x][y] = counter++;
x += direction[i][0];
y += direction[i][1];
}
}
}
return matrix;
}