FOR FREE CONTENT

Spiral Matrix

Back to Programming

Description

The word ‘spiral’ means winding in a continuous and widening curve which is either surrounding a central point on a flat plane or about an axis.

This program is to print the matrix in a spiral form.

Let the matrix be:

 

Now, if we draw a spiral like structure over the matrix we will get:

 

So, if we print this matrix in spiral form we will get: 1, 2, 3, 6, 9, 8, 7, 4, 5.

Algorithm

INPUT: A matrix
OUTPUT: the matrix in spiral form

PROCESS:
Step 1: [taking the inputs]
	Read m, n [the rows and columns of the matrix]
	For i=0 to m-1 repeat
		For j=0 to n-1 repeat
			Read a[i][j]
		[End of ‘for’ loop]
	[End of ‘for’ loop]
Step 2: [displaying the spiral form]
Set i<-0
Set j<-0
	while i < m and j < n repeat 
        		[Printing the first row from the remaining]
        		for k = j to n-1 repeat 
            			print a[i][k] 
        		[End of ‘for’ loop]
        		Set i<-i+1 
        		[Printing the last column from the remaining]
        		for k = i to m-1 repeat 
            			print a[k][n - 1] 
        		[End of ‘for’ loop]
        		Set n<-n-1 
        		[Print the last row from the remaining]
        		if i< m then 
            			for k= n – 1 to j repeat 
                			print a[m - 1][k] 
            			[End of ‘for’ loop] 
            			Set m<-m-1 
        		[End of ‘if’]
        		[Print the first column from the remaining]
        		if j< n then 
            			for k= m – 1 to I repeat 
                			print a[k][j] 
            			[End of ‘for’ loop]
            			Set j<-j+1 
        		[End of ‘for’ loop]
    	[End of ‘while’ loop]
Step 3: Stop.

TIME COMPLEXITY:

while (i < m && j < n) ------------------ O(n)

{      //Printing the first row from the remaining

        for (k = j; k < n; k++) { ------------ O(n-j)

            printf("%d ",a[i][k]); 

        } 

        i++; ------------------------------------ O(1)

 

        //Printing the last column from the remaining

        for (k = i; k< m; k++) { -------------- O(m-i)

            printf("%d ",a[k][n - 1]); 

        }

        n--; -------------------------------------- O(1)

        //Print the last row from the remaining

        if (i< m) { ------------------------------- O(c1)

            for (k= n - 1; k>= j; k--) { --------- O(n-1-j+1)

                printf("%d ",a[m - 1][k]);; 

            } 

            m--; ------------------------------------ O(1)

        } 

        //Print the first column from the remaining

        if (j< n) { ---------------------------------- O(c2) 

            for (k= m - 1; k >= i; k--) { ---------- O(m-1-i+1)

                printf("%d ",a[k][j]); 

            } 

            j++; ---------------------------- O(1)

        }

    } 

Here c1 and c2 are constant so, the time complexity is O(n2).