Print n x n spiral matrix using C program, using O(1) extra space

Given a positive integer n, and construct an n x n spiral matrix, using only O(1) extra space in the clockwise direction

A spiral matrix is ​​a matrix that works like a spiral, it will Start from the origin of the circle and rotate in a clockwise direction. So the task is to print the matrix in spiral form using O(1) space starting from 2 → 4 → 6 → 8 → 10 → 12 → 14 → 1 6→ 18.

Below is an example spiral matrix -

Example

Input: 3
Output:
   9 8 7
   2 1 6
   3 4 1

It becomes easy to solve code with infinite space, but it doesn’t Efficient like an optimal program, or code that is both memory and time efficient. So to maintain the spiral order four loops are used, one each for the upper, right, lower and left corners of the matrix, but if we divide the matrix into two parts, the upper right and lower left corners, we can directly use This concept

For the upper right half,

mat[i][j] = (n-2*x)*(n-2*x)-(i-x)-(j-x)

For the lower left half,

mat[i][j] = (n-2*x-2)*(n-2*x-2) + (i-x) + (j-x)

Note-We are writing for print 2 Program for multiples of matrices

Algorithm

int spiralmatrix(int n)
START
STEP 1: DECLARE i, j, a, b, x
STEP 2: LOOP FOR i = 0 AND i < n AND i++
   LOOP FOR j = 0 AND j < n AND j++
      FIND THE MINIMUM IN (i<j ) AND ASSIGN IT TO a
      FIND THE MINIMUM (n-1-i) < (n-1-j) AND ASSIGN IT TO b
      THEN ASSIGN THE LEAST VALUE FROM a AND b TO x
      IF i <= j THEN,
         PRINT THE VALUE OF 2* ((n-2*x)*(n-2*x) - (i-x) - (j-x))
      ELSE
         PRINT THE VALUE OF 2*((n-2*x-2)*(n-2*x2) + (i-x) + (j-x))
   END LOOP
   PRINT NEWLINE
END LOOP
STOP

Example

#include <stdio.h>
//For n x n spiral matrix
int spiralmatrix(int n){
   int i, j, a, b, x; // x stores the layer in which (i, j)th element exist
   for ( i = 0; i < n; i++){
      for ( j = 0; j < n; j++){
         // Finds minimum of four inputs
         a = ((i<j ? i : j));
         b = ((n-1-i) < (n-1-j) ? (n-1-i) : (n-1-j));
         x = a < b ? a : b;
         // For upper right half
         if (i <= j)
            printf("%d\t ", 2 * ((n-2*x)*(n-2*x) - (i-x) - (j-x)));
            // for lower left half
         else
            printf("%d\t ", 2*((n-2*x-2)*(n-2*x-2) + (i-x) + (j-x)));
      }
      printf("</p><p>");
   }
}
int main(int argc, char const *argv[]){
   int n = 3;
   spiralmatrix(n);
   return 0;
}

Output

If we run the above program then it will generate the following output -

18 16 14
4 2 12
6 8 10

The above is the detailed content of Print n x n spiral matrix using C program, using O(1) extra space. For more information, please follow other related articles on the PHP Chinese website!