volatile keyword in C / C++
June 12, 2012
Turn off the rightmost bit of an integer
June 12, 2012

Traversing a matrix in spiral order

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--;
    }
}

 

8 Comments

  1. chinky4u says:

    can i please see the code?

  2. Kuchu says:

    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.

    • Kamal Rawat says:

      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..

  3. Olivia Biswas says:

    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. olivia says:

    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–;.
    }
    }

  5. but this code works only for square matrix. can you give a more generalized code for any matrix size.

  6. Huy says:

    does anybody have code on FREE PASCAL???

Leave a Reply to Commenter 55 Cancel reply

Your email address will not be published. Required fields are marked *