Jun 122012
 

Given a Matrix, write a function that will print the elements in spiral order. For example, if the Matrix is as below:

Then the output should be:

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

Which is the spiral order of given matrix:

Solution:

The given matrix is below:

 

In a single loop we will print one complete circle of elements. Hence we will have 4 loops inside a bigger loop to print the

1. Top Row from Left to Right
2. Last Column from Top to bottom
3. Last Row from Right to Left
4. First Column Bottom to Top

So first pass (of outer loop, which has the above 4 loops) the elements will get printed as below:

In the next loop we will print the inner circle

And so on..

Code:

void spiralTraversal(int **a, int n)
{
    int rs=0, cs=0;     // RowStart and Column Start
    int re=n-1, ce=n-1;  // RowEnd & columnEnd
    
    while(rs<=re && cs<=ce)
    {
        int i=rs, j=cs;
        
        for(j=cs; j<=ce; j++)
            cout<<" "<<a[i][j];
            
        for(i=rs+1, j--; i<=re; i++)
            cout<<" "<<a[i][j];
            
        for(j=ce-1, i--; j>=cs; j--)
            cout<<" "<<a[i][j];
            
        for(i=re-1, j++; i>=rs+1; i--)
            cout<<" "<<a[i][j];
             
        rs++; cs++; re--; ce--;
    }
} 

 

  7 Responses to “Traversing a matrix in spiral order”

Comments (7)
  1. but this code works only for square matrix. can you give a more generalized code for any matrix size.

  2. This will not work for cases where row and column sizes are different and specially in cases where rowstart equals rowend and columnstart equals columnend. in those cases there will be duplicacy of the results printed.
    working code :

    void traverseMatrixSpirally(int ** a, int numOfRows , int numOfCols).
    {
    int cs = 0;.
    int rs = 0;.
    int ce = numOfCols-1;.
    int re = numOfRows-1;.
    int i, j;

    while(rs<= re && cs <= ce).
    {

    for (i = rs, j = cs ; j<= ce; j++).
    Console::Write(" " + a[i][j]);.

    if(rs==re)
    return;

    for(j–, i=rs+1;i=cs; j–).
    Console::Write(” ” + a[i][j]);.

    for(j++, i=re-1;i>=rs+1;i–)
    Console::Write(” ” + a[i][j]);.
    cs++; rs++; ce–; re–;.
    }
    }

  3. This will not work for cases where row and column sizes are different and specially in cases where rowstart equals rowend and columnstart equals columnend. in those cases there will be duplicacy of the results printed.
    working code :

    void traverseMatrixSpirally(int ** a, int numOfRows , int numOfCols).
    {
    int cs = 0;.
    int rs = 0;.
    int ce = numOfCols-1;.
    int re = numOfRows-1;.
    int i, j;

    while(rs<= re && cs <= ce).
    {

    for (i = rs, j = cs ; j<= ce; j++).
    Console::Write(" " + a[i][j]);.

    if(rs==re)
    return;

    for(j–, i=rs+1;i<=re;i++)
    Console::Write(" " + a[i][j]);.
    if(cs==ce)
    return;

    for(i–, j=ce-1; j>=cs; j–).
    Console::Write(" " + a[i][j]);.

    for(j++, i=re-1;i>=rs+1;i–)
    Console::Write(" " + a[i][j]);.
    cs++; rs++; ce–; re–;.
    }
    }

  4. i think this is doing something different. You very first for loop is going down on the left instead of going right at the top. IOW, I don’t think you should be fixing i and incrementing j.

    • The main for loop has 4 loops.. the first inner loop will traverse the top row (left to right), second the last column (Top to Down), 3rd will traverse the last row (Right to Left) and final will traverse the first column (Bottom-Up)..

      Once the first pass is over (two top/bottom rows and left/right columns are printed).. then the moves on to print the inner matrix.. the start point will be (1,1) hence 2nd row from top will be printed, similarly the 2nd last column will be printed followed by 2nd last row and 2nd column..

      And so on..

  5. can i please see the code?

 Leave a Reply

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

(required)

(required)