Input:
Output:
1 2 3 4
12 13 14 5
11 16 15 6
10 9 8 7
Approach
- Create an n-dimensional 2D array.
- In the boundary variable, store the array's boundaries. It will start with n-1 and will change after each revolution.
- In variable sizeLeft , save the size left for spiral printing. It will start at n-1 and decrease by 1 after every two rotations.
- Create a flag to identify two revolutions, as the sizeLeft will drop after every two rotations.
- Create a char attribute move for storing the spiral pattern's present movement. It may contain the letters 'r' for right, 'l' for left, 'd' for down, and 'u' for up.
- Repeat the following steps until 'i' is in the range [1, n2] :
- Assign an i value to the spiral pattern.
- Determine the next pattern's movement.
- Check to see if the pattern has reached the boundary. Change the sizes and spin the spiral design if you reach this point.
- Print the pattern as a 2D array.
Program to spiral pattern in C
Let's consider an example to demonstrate the spiral arrangement in the C programming language.
Filename: Pattern. c
#include <stdio.h>
void generateSpiral(int n) {
int matrix[n][n];
int top = 0, bottom = n - 1, left = 0, right = n - 1;
int num = 1;
while (top <= bottom && left <= right) {
// Move right
for (int i = left; i <= right; i++) {
matrix[top][i] = num++;
}
top++;
// Move down
for (int i = top; i <= bottom; i++) {
matrix[i][right] = num++;
}
right--;
// Move left
for (int i = right; i >= left; i--) {
matrix[bottom][i] = num++;
}
bottom--;
// Move up
for (int i = bottom; i >= top; i--) {
matrix[i][left] = num++;
}
left++;
}
// Print the generated spiral matrix
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
printf("%2d ", matrix[i][j]);
}
printf("\n");
}
}
int main() {
int n;
printf("Enter the size of the square matrix: ");
scanf("%d", &n);
generateSpiral(n);
return 0;
}
Output:
Enter the size of the square matrix: 3
1 2 3
8 9 4
7 6 5
Enter the size of the square matrix: 9
1 2 3 4 5 6 7 8 9
32 33 34 35 36 37 38 39 10
31 56 57 58 59 60 61 40 11
30 55 72 73 74 75 62 41 12
29 54 71 80 81 76 63 42 13
28 53 70 79 78 77 64 43 14
27 52 69 68 67 66 65 44 15
26 51 50 49 48 47 46 45 16
25 24 23 22 21 20 19 18 17
Explanation
- The generateSpiral function accepts an integer n as an input, representing the square matrix size.
- A 2D integer array matrix of size n x n is declared inside the method to store the spiral pattern.
- The borders of the matrix are represented by four variables: top, bottom, left, and right. The top is initially set to 0 , the bottom to n - 1 , the left to 0 , and the right to n - 1 .
- Another integer variable, num , has been set to 1 . This variable records the value to be filled in the matrix, beginning with 1.
- The program enters in a while loop , repeated until the top boundary is less than or equal to the bottom boundary and the leftmost boundary is less than or equal to the right boundary. This loop ensures that the spiral pattern is accurately created.
- Four loops are used within the loop to fill the matrix in four directions: right, down, left, and up. Each of the directions takes up one side of the spiral.
- Move Right: The first loop traverses the row from left to right, filling it with values ranging from num to num + (right - left) .
- Move Down: The second loop proceeds from top to bottom, filling the right-hand column with values ranging from num to num + (bottom - top) .
- Move Left: The third loop proceeds from right to left, filling the row at the bottom border in reverse order with values ranging from num to num + (right - left) .
- Move Up: The fourth loop advances from bottom to top, filling every column at the left border in reverse order with values ranging from num to num + (bottom - top) .
- After filling each direction, the relevant boundary (top, bottom, left, or right) is modified to show that one side of the spiral is complete.
- After each value in the matrix is filled, the num variable is incremented.
- When the loop is finished, the created spiral pattern is printed through iterating through the matrix array, and each element is formatted properly.
- The main function accepts the size of the square matrix (n) from user input and runs the generate spiral function to produce and print the spiral pattern.
Time Complexity (O(n^2)):
The primary iteration within the generateSpiral function continues until the upper boundary is less than or equal to the lower boundary, and the left boundary is less than or equal to the right boundary. This loop will execute for n/2 cycles at most, as the top, bottom, left, and right limits progressively approach the center of the matrix.
We possess four interconnected loops that cycle through the rows and columns of the matrix during every loop iteration. These nested loops iterate multiple times in both horizontal and vertical directions.
Consequently, the maximum number of iterations in the worst-case scenario is roughly 4 times n divided by 2 times n, simplifying to O(n^2).
Space Complexity(O(n^2)):
The space complexity is influenced by the dimensions of the matrices array, specified as int matrixn. This array comprises n rows and n columns, accommodating a total of n² entries.
Each matrix array element stores an integer value.
Consequently, the space complexity amounts to O(n^2) as it significantly increases in proportion to the input size n.