Printing the matrix in spiral format is a common array question that is asked in the onsite interviews. It is a square matrix that one traverses in following directions:
- Left to right
- Top to bottom
- Bottom to Top
- Right to Left
If a specific element is outputted then it won't be outputted. Here is a sample:
Input: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
Output: 1 2 3 4 8 12 16 15 14 13 9 5 6 7 11 10
Here is the algorithm along with a dry run:
Algorithm :
Step 1: Declare and initialize a 4x4 matrix(2D array) “a” with the given values 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16.
Matrix a,
Step 2: Declare and initialize a variable “n” with the value 4 (length of 2D array(matrix)).
n = 4
Step 3: Declare and initialize required variables to track rows and columns while printing the matrix in spiral form.
row = 0
col = 0
row_now = 0
col_now = 0
Step 4: Using while loop to iterate the matrix in spiral form by repeating the next six steps till the condition fails.
Step 5: Assign present row and column values to the variables.
row = row_now
col = col_now
Step 6: Moving to the right -> print the first row from the remaining rows.
Step 7: Moving down -> print the last column from the remaining columns.
Step 8: Moving to the left -> print the last row from the remaining rows.
Step 9: Moving up -> print the first column from the remaining columns.
Step 10: For the next iteration decrement the length of matrix and increment the present row and column values.
Iteration 1: (step 4)
n = 4
(4-1) != 1
3 != 1 -> condition true
Present row and col : (step 5)
row = 0
col = 0
Right : (step 6)
IF, 0==0 and 0==0 -> condition true
Iteration 1.1 :
0 != 3 -> condition true
Print a[0][0] = 1
Output : 1
col=1 (incremented by 1)
Iteration 1.2 :
1 != 3 -> condition true
Print a[0][1] = 2
Output : 1 2
col=2 (incremented by 1)
Iteration 1.3 :
2 != 3 -> condition true
Print a[0][2] = 3
Output : 1 2 3
col=3 (incremented by 1)
Iteration 1.4 :
3 != 3 -> condition false.
Terminate the inner loop for right.
Down : (step 7)
IF, 3==3 and 0==0 -> condition true
Iteration 1.1 :
0 != 3 -> condition true
Print a[0][3] = 4
Output : 1 2 3 4
row=1 (incremented by 1)
Iteration 1.2 :
1 != 3 -> condition true
Print a[1][3] = 8
Output : 1 2 3 4 8
row=2 (incremented by 1)
Iteration 1.3 :
2 != 3 -> condition true
Print a[2][3] = 12
Output : 1 2 3 4 8 12
row=3 (incremented by 1)
Iteration 1.4 :
3 != 3 -> condition false.
Terminate the inner loop for down.
Left : (step 8)
IF, 3==3 and 3==3 -> condition true
Iteration 1.1 :
3 != 0 -> condition true
Print a[3][3] = 16
Output : 1 2 3 4 8 12 16
col=2 (decremented by 1)
Iteration 1.2 :
2 != 0 -> condition true
Print a[3][2] = 15
Output : 1 2 3 4 8 12 16 15
col=1 (decremented by 1)
Iteration 1.3 :
1 != 0 -> condition true
Print a[3][1] = 14
Output : 1 2 3 4 8 12 16 15 14
col=0 (decremented by 1)
Iteration 1.4 :
0 != 0 -> condition false.
Terminate the inner loop for left.
Up : (step 9)
IF, 0==0 and 3==3 -> condition true
Iteration 1.1 :
3 != 0 -> condition true
Print a[3][0] = 13
Output : 1 2 3 4 8 12 16 15 14 13
row=2 (decremented by 1)
Iteration 1.2 :
2 != 0 -> condition true
Print a[2][0] = 9
Output : 1 2 3 4 8 12 16 15 14 13 9
row=1 (decremented by 1)
Iteration 1.3 :
1 != 0 -> condition true
Print a[1][0] = 5
Output : 1 2 3 4 8 12 16 15 14 13 9 5
row=0 (decremented by 1)
Iteration 1.4 :
0 != 0 -> condition false.
Terminate the inner loop for up.
n = 3 (decremented by 1) (step 10)
row_now = 1 (incremented by 1)
col_now = 1 (incremented by 1)
Iteration 2 :
n = 3
(3-1) != 1
2 != 1 -> condition true
Present row and col :
row = 1
col = 1
Right :
IF, 1==1 and 1==1 -> condition true
Iteration 2.1 :
1 != 2 -> condition true
Print a[1][1] = 6
Output : 1 2 3 4 8 12 16 15 14 13 9 5 6
col=2 (incremented by 1)
Iteration 2.2 :
2 != 2 -> condition false.
Terminate the inner loop for right.
Down :
IF, 1==1 and 1==1 -> condition true
Iteration 2.1 :
1 != 2 -> condition true
Print a[1][2] = 7
Output : 1 2 3 4 8 12 16 15 14 13 9 5 6 7
row=2 (incremented by 1)
Iteration 2.2 :
2 != 2 -> condition false.
Terminate the inner loop for down.
Left :
IF, 2==2 and 2==2 -> condition true
Iteration 2.1 :
2 != 0 -> condition true
Print a[2][2] = 11
Output : 1 2 3 4 8 12 16 1 5 14 13 9 5 6 7 11
col=1 (decremented by 1)
Iteration 2.2 :
1 != 0 -> condition true.
Print a[2][1] = 10
Output : 1 2 3 4 8 12 16 1 5 14 13 9 5 6 7 11 10
col=0 (decremented by 1)
Iteration 2.3 :
0 != 0 -> condition false.
Terminate the inner loop for left.
Up :
IF, 0==1 and 2==2 -> condition false.
Terminate the inner loop for up.
n=2 (decremented by 1)
row_now = 2
col_now = 2
Iteration 3:
(n-1) != 1
(2-1) != 1
1 != 1 -> Condition false
Terminate the outer loop.
Implementation:
#include <iostream>
#include <conio.h>
#include <stdio.h>
using namespace std;
int main()
{
int a[4][4] = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16};
int n = 4;
//Initializations
int row_now = 0,row = 0;
int col_now = 0,col = 0;
while(n-1 != 1)
{
row = row_now;
col = col_now;
//Moving to the right
if(row == row_now && col == col_now)
while(col!=n-1)
cout<<a[row][col++]<<" ";
//Moving down
if(col==n-1 && row == row_now)
while(row!=n-1)
cout<<a[row++][col]<<" ";
//Moving left
if(col == n-1 && row == n-1)
while(col!=0)
cout<<a[row][col--]<<" ";
//Moving up
if(col == col_now && row == n-1)
while(row!=0)
cout<<a[row--][col]<<" ";
//Getting ready for the next iteration
n--;
row_now++;
col_now++;
}
getch();
return 0;
}
Output :
1 2 3 4 8 12 16 15 14 13 9 5 6 7 11 10
Algorithm complexity :
O(m*n) m = row and n = column
No comments:
Post a Comment