Spiral matrix: Spiral order traversal of matrix

Spiral matrix : Print matrix in spiral order

Given a N x M matrix, print all elements in it in spiral order.This problem is also called as spiral matrix problem. For example,

1,2,3,4
5,6,7,8
9,10,11,12

Output should be 1,2,3,4,8,12,11,10,9,5,6,7

Below diagram explains spiral traversal.
spiral matrix

Spiral order traversal will be 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25

This problem is commonly asked in interviews because it can be easily solved in 30 to 40 minutes and tests your ability to work with array indices very well. Whole problem is about adjusting array indices.

Spiral matrix algorithm

Can you figure out what we did in example above? We traversed first row, then last column, last row and then first column. Once done we move inside and our size of matrix now becomes N-2 and M-2 as we have already traversed two rows and column in first round. Again traverse, second row from second column, till newly adjusted column length. Traverse last column starting between newly adjusted rows, as first and last are already traversed. Go on till we have traversed all elements.

Implementation wise, have four variables currentRow, currentColumn, row and column, Adjust these four variables to achieve what is described above.

Figure shows how the traversal happens.
spiral order traversal

Spiral matrix implementation

#include<stdio.h>
#include<stdlib.h>

void spiralMatrix(int a[][5], int row, int col){

      int currentRow=0, currentColumn=0;
      int i;
      while(currentRow < row && currentColumn <col){
        /* Print the first row and next row starts with
        increased column so increment column count */
        for(i=currentColumn; i<col; i++)
          printf("%d ", a[currentRow][i]);
        currentRow++;

	/* Print the last column, next time we need to
	print second to last column, hence decrement col */
        for(i=currentRow; i<row; i++)
           printf("%d ", a[i][col-1]);
        col--;

	/* If we have not reached at the end 
	print column in reverse order*/
        if(currentRow<row){
           for(i=col-1; i>=currentColumn; i--)
              printf("%d ", a[row-1][i]);
           row--;
        }
        
        /* If we have not reached at the end,
        print row in reverse order */
        if(currentColumn<col){
           for(i=row-1; i>=currentRow; i--)
              printf("%d ", a[i][currentColumn]);
           currentColumn++;
        }
      }
      printf("\n");
}

/* Driver program */
int main(){
	int a[5][5] = {1,2,3,4,5,
                        6,7,8,9,10,
                        11,12,13,14,15,
                        16,17,18,19,20,
                        21,22,23,24,25};
	spiralMatrix(a,5,5);
	return 0;
}

Thanks Prince Mishra for python code.

def spiral_traversal(matrix):
    size = len(matrix)
    total = len(matrix)*len(matrix)
    i = 0
    start_row = 0
    end_row = size-1

    start_col = 0
    end_col = size-1

    dir = 0

    while i<total:

        if dir == 0:
            # ltr
            j = start_col
            while j <= end_col:
                print matrix[start_row][j]
                j+=1
                i += 1

            start_row +=1
            dir = 1

        if dir == 1:
            j = start_row
            while j <= end_row:
                print matrix[j][end_col]
                j+=1
                i+=1
            end_col -=1
            dir = 2

        if dir == 2:
            j = end_col
            while j>=start_col:
                print matrix[end_row][j]
                j-=1
                i+=1
            end_row -=1
            dir = 3

        if dir == 3:
            j = end_row
            while j>=start_row:
                print matrix[j][start_col]
                j-=1
                i+=1
            start_col+=1
            dir = 0

arr = [
    [1,2,3,4],
    [5,6,7,8],
    [9,10,11,12],
    [13,14,15,16]
]

spiral_traversal(arr)

Complexity of spiral matrix algorithm is O(n2).

Please share if there is something wrong or missing. If you are interested in contributing to algorithms and me, please contact us.