In the Leetcode Spiral Matrix II problem solution 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
Solution in C Programming
int** generateMatrix(int n, int* returnSize, int** returnColumnSizes){
*returnSize = n;
*returnColumnSizes = malloc(n*sizeof(int*));
int** out = malloc(n*sizeof(int*));
/* lower and upper limits for i index and j index (decrements as spiral gets tighter) */
int ilower = 1;
int jlower = 0;
int iupper = n-1;
int jupper = n-1;
int steps = 0;
int num = 1;
int temp = 0;
for (int i = 0; i < n; i++) {
(*returnColumnSizes)[i] = n;
out[i] = malloc(n*sizeof(int));
}
/* n = 1 returns [[1]] */
if (n == 1) {
out[0][0] = 1;
return out;
}
/* total steps up and down the 2d array = n + (n-1) */
while (steps != n + (n-1)) {
/* going right */
if (steps % 4 == 0) {
for (temp = jlower; temp <= jupper; temp++, num++) {
out[ilower-1][temp] = num;
}
jupper--;
}
/* going down */
else if (steps % 4 == 1) {
for (temp = ilower; temp <= iupper; temp++, num++) {
out[temp][iupper] = num;
}
iupper--;
}
/* going left */
else if (steps % 4 == 2) {
for (temp = jupper; temp >= jlower; temp--, num++) {
out[iupper+1][temp] = num;
}
jlower++;
}
/* going up */
else if (steps % 4 == 3) {
for (temp = iupper; temp >= ilower; temp--, num++) {
out[temp][jlower-1] = num;
}
ilower++;
}
steps++;
}
return out;
}Solution in C++ Programming
class Solution {
public:
vector<vector<int>> generateMatrix(int n) {
int r1 = 0, r2 = n-1;
int c1 = 0, c2 = n-1;
int val = 0;
// result matrix
vector<vector<int>> v(n, vector<int> (n));
while(r1 <= r2 && c1 <= c2)
{
// left to right (row will be fixed)
for(int i = c1; i <= c2; ++i)
v[r1][i] = ++val;
// move down(col will be fixed)
for(int i = r1+1; i <= r2; ++i)
v[i][c2] = ++val;
// move right to left
// move up
if(r1 < r2 && c1 < c2)
{
// move right to left (row will be fixed)
for(int i = c2-1; i>c1; --i)
v[r2][i] = ++val;
// move up (col will be fixed)
for(int i = r2; i>r1; --i)
v[i][c1] = ++val;
}
++r1;
--r2;
++c1;
--c2;
}
return v;
}
};Solution in Java Programming
class Solution {
public int[][] generateMatrix(int n) {
int c = 1;
int[][] result = new int[n][n];
for(int i = 0 ; i < (n + 1) / 2 ; i++) {
for(int x = i ; x < n - i ; x++) {
result[i][x] = c++;
}
for(int y = i + 1 ; y < n - i ; y++) {
result[y][n - i - 1] = c++;
}
for(int x = n - i - 2 ; x >= i ; x--) {
result[n - i - 1][x] = c++;
}
for(int y = n - i - 2 ; y >= i + 1 ; y--) {
result[y][i] = c++;
}
}
return result;
}
}
Solution in Python Programming
class Solution(object):
def generateMatrix(self, n):
L, R, T, B = 0, n-1, 0, n-1
mat = [[0 for _ in range(n)] for _ in range(n)]
curr = 1
while L < R:
for i in range(L, R):
mat[T][i] = curr
curr += 1
for i in range(T, B):
mat[i][R] = curr
curr += 1
for i in range(R, L, -1):
mat[B][i] = curr
curr += 1
for i in range(B, T, -1):
mat[i][L] = curr
curr += 1
L, R, T, B = L+1, R-1, T+1, B-1
if n%2 != 0: mat[T][B] = curr
return matSolution in C# Programming
public class Solution {
public int[][] GenerateMatrix(int n) {
int [][] res = Enumerable.Range(0, n).Select(i=>new int[n]).ToArray();
Solutions s=new Solutions();
var result=s.sprialMatrix2(0,0,n,res,1);
return result;
}
}
class Solutions{
public int [][] sprialMatrix2(int i,int j,int n,int [][] matrix,int count){
if(i>=n || j>=n) return matrix;
for(int p=i;p<n;p++){
matrix[i][p]=count++;
}
for(int p=i+1;p<n;p++){
matrix[p][n-1]=count++;
}
if(n-1!=i){
for(int p=n-2;p>=j;p--){
matrix[n-1][p]=count++;
}
}
if(n-1!=j){
for(int p=n-2;p>i;p--){
matrix[p][j]=count++;
}
}
return sprialMatrix2(i+1,j+1,n-1,matrix,count);
}
}Also read,