# Rearrange elements in two-dimensional array spiral order

Recently I was asked to write algorithm to rearrange elements in two-dimensional array in spiral order.

Input array: Output array:

[  1,  2,  3,  4]           [  1,  2,  3,  4 ]
[  5,  6,  7,  8]    = >    [  8, 12, 11, 10 ]
[  9, 10, 11, 12]           [  9,  5,  6,  7 ]


I came up with the following solution using JavaScript:

(function(){
var Spiralify = function(matrix){
function isArray(obj){
return Object.prototype.toString.call(obj) === '[object Array]'
}

//Matrix is not specified or not an array
if( !matrix || !isArray(matrix) ) { console.log('Matrix is not an array'); return; }

var rows = matrix.length;
if( rows <= 1 ) return matrix;
//If first element of matrix is not an array, we cant define amount of columns in matrix, so just wrap it in array and return
if(!isArray(matrix[0])) return [matrix];

var cols = matrix[0].length;
//If rows of the matrix are empty arrays, return null
if( cols == 0 ) return matrix;

//If arrays, corresponding to rows, have different amount of elements, return null
if(matrix.some(function(el){ return el.length != cols; })) { console.log('All rows must have equal amount of columns'); return; }

//If we have only one column, just transpond the array and wrap it into another array
if( cols == 1) return [matrix.map(function(i){ return i[0]; })];

function getUpperCorner(r1,c1,r2,c2)
{
for(var i=c1;i<=c2;i++)
tmpArray.push(matrix[r1][i]);

for(var j=r1+1;j<=r2;j++)
tmpArray.push(matrix[j][c2]);

if(r2-r1 > 0)
getLowerCorner(r1+1,c1,r2,c2-1);
}

function getLowerCorner(r1,c1,r2,c2)
{
for(var i=c2;i>=c1;i--)
tmpArray.push(matrix[r2][i]);

for(var j=r2-1;j>=r1;j--)
tmpArray.push(matrix[j][c1]);

if(r2-r1 > 0)
getUpperCorner(r1,c1+1,r2-1,c2);
}

var tmpArray = [];
getUpperCorner(0,0,rows-1,cols-1);

var result = new Array(rows);
for(var i=0;i<rows;i++)
result[i] = tmpArray.splice(0,cols);

return result;
}

var matrix1 = [[1,2,3,4,5],[6,7,8,9,10],[11,12,13,14,15]];
var matrix2 = [[1,2,3,4,5],[6,7,8],[11,12,13,14,15]];
var matrix3 = [[1,2,3,4]];
var matrix4 = [[1],[2],[3],[4],[5],[6]];
var matrix5 = null;
var matrix6 = 1234;
var matrix7 = [];
var matrix8 = [[],[],[]];
var matrix9 = [1,2,3,4];
var matrix10 = 'Hello';

console.log (Spiralify(matrix1));
console.log (Spiralify(matrix2));
console.log (Spiralify(matrix3));
console.log (Spiralify(matrix4));
console.log (Spiralify(matrix5));
console.log (Spiralify(matrix6));
console.log (Spiralify(matrix7));
console.log (Spiralify(matrix8));
console.log (Spiralify(matrix9));
console.log (Spiralify(matrix10));
})(window);


But this solution was a show-stopper. I'm trying to learn from the defeat and would really appreciate some feedback on why this code is unappropriate.

I'm not sure what exactly about your code made it a "show-stopper." Your use of tmpArray has a bit of a smell to it. There are issues of readability (why does the line for(var i=c1;i<=c2;i++) only have one space in it??). Your core algorithm (getUpperCorner and getLowerCorner) isn't documented and is fairly hard to read.

Personally, though, I would have approached this as a straight recursion problem. So you have the following matrix:

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


Your "spiral" begins with the the top row, 1 2 3 4. So chop that off and save it.

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


Now you'll notice that the rightmost column of the remaining part, 8 12, is the next part of the spiral. But what if we turn it 90º counter-clockwise?

 5  6  7  8  =>   8 12
9 10 11 12       7 11
6 10
5  9


Now 8 12 the top row! Chop it off and repeat:

   8 12
✂ ┄┄┄┄┄┄
7 11  =>  11 10  9  =>    11 10  9
6 10       7  6  5     ✂ ┄┄┄┄┄┄┄┄┄┄
5  9                       7  6  5  =>  5  =>   5
6    ✂ ┄┄┄
7       6  =>  6  7  (end!)
7


By now you've seen the pattern. To get a matrix's "spiral" you just take off the top row, rotate what's left, then get its spiral, and so on.

Def Spiralify( Matrix )
If( Matrix has only one row )
Return( the row )

Else
FirstRow     := first row of Matrix
RestOfMatrix := all of Matrix except the first row

NextMatrix := RotateLeft( RestOfMatrix )

NextSpiral := Spiralify( NextMatrix )

Result := JoinArrays( FirstRow, NextSpiral )

Return( Result )


RotateLeft will actually make up the most lines of code, but it's just a straightforward nested loop, and the rest basically writes itself.

## Update

I had some time to write up an actual implementation. Rather than paste it here you can check it out on jsFiddle.