This is a series of implementation problems for beginners in programming. The first part is on spiral traversal in two dimensional array.
Question:
Given a two dimensional array with n row and m column.
We need to give the output a one-dimensional array in spiral order.
input:
inputArray[][] ={
{1, 2, 3, 4},
{12,13,14,5},
{11,16,15,6},
{10, 9, 8, 7},
}
output:
{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16}
Solution
Traverse the given array in right, down, left, and upward directions.
One corner case is that we need to check if the total element in the spiral 1D array is already equal to row*column.
vector<int> spiralTraverse(vector<vector<int>> array) {
int column = array[0].size();
int row = array.size();
vector<int>spiralArray; // output array
int i = 0, j = 0, x = 0;
int rowCount = row -1;
int columnCount = column;
int count=0;
while (spiralArray.size() < row*column) {
x = 0;
while (x < columnCount) {
spiralArray.push_back(array[i][j]);
j++, x++; count++;
} //traverse right side through columns
j--;
columnCount--;
i++; x = 0;
if(count < row*column)
while (x < rowCount) { // traverse downwards through rows
spiralArray.push_back(array[i][j]);
i++, x++; count++;
}
rowCount--;
x = 0, i--;
j--;
if(count < row*column)
while (x < columnCount) { // traverse left side
spiralArray.push_back(array[i][j]);
j--, x++; count++;
}
columnCount--;
j++;
i--;
x = 0;
if(count < row*column)
while (x < rowCount) { // traverse upward through rows
spiralArray.push_back(array[i][j]);
i--, x++; count++;
}
rowCount--;
i++;
j++;
}
return spiralArray;
}
Top comments (0)