Wednesday, May 6, 2015

Microsoft Question: Spiral order traversal of a matrix

Problem: Given a 2D array, print it in spiral form.

Implementation:

void spiralPrint(int **arr, int row, int col)
{
if(row == 0 || col == 0 || arr == 0)
return;
if(row == 1 && col == 1)
std::cout<<arr[0][0]<<'\t';
int cBeg = 0, cEnd = col, rBeg = 0, rEnd = row;
while(cBeg < cEnd && rBeg < rEnd)
{
for(int i = cBeg; i < cEnd; ++i)
std::cout<<arr[rBeg][i]<<'\t';
++rBeg;
for(int i = rBeg; i <rEnd; ++i)
std::cout<<arr[i][cEnd - 1]<<'\t';
--cEnd;
if(rBeg < rEnd)
{
for(int i = cEnd - 1; i >= cBeg; --i)
std::cout<<arr[rEnd - 1][i]<<'\t';
--rEnd;
}
if(cBeg < cEnd)
{
for(int i = rEnd - 1; i >= rBeg; --i)
std::cout<<arr[i][cBeg]<<'\t';
++cBeg;
}
}
}

Complexity: O(row*col)

No comments:

Post a Comment