Spiral traversal of matrix-recursive solution in JavaScript
I am trying to find a solution that accepts a matrix like this:
[[1,2,3,4],
[5,6,7,8],
[9,10,11,12],
[13,14,15,16]]
and returns an array moving the array like a spiral, so in this example:
[1,2,3,4,8,12,16,15,14,13,9,5,6,7,11,10]
I'm having trouble getting this recursive solution to work, where the result array takes the first array, the final elements of the rest of the arrays, the bottom array in reverse order, and then the first elements of the middle arrays, and then converts the array without that outer "wrapper" so that it can be recursively caused by what's left until there is a single element array in the center or a 2x2 matrix (my basic cases, although the latter may not be needed ...)
My solution that doesn't work looks like this. Any suggestions on how I can make this work?
var spiralTraversal = function(matriks){
var result = [];
var goAround = function(matrix) {
var len = matrix[0].length;
if (len === 1) {
result.concat(matrix[0]);
return result;
}
if (len === 2) {
result.concat(matrix[0]);
result.push(matrix[1][1], matrix[1][0]);
return result;
}
if (len > 2) {
// right
result.concat(matrix[0]);
// down
for (var j=1; j < matrix.length - 1; j++) {
result.push(matrix[j][matrix.length -1]);
}
// left
for (var l=matrix.length - 2; l > 0; l--) {
result.push(matrix[matrix.length - 1][l]);
}
// up
for (var k=matrix.length -2; k > 0; k--) {
result.push(matrix[k][0]);
}
}
// reset matrix for next loop
var temp = matrix.slice();
temp.shift();
temp.pop();
for (var i=0; i < temp.length - 1; i++) {
temp[i] = temp[i].slice(1,-1);
}
goAround(temp);
};
goAround(matriks);
};
+9
source to share
12 replies
Your code is very close, but it does more than it needs to be. Here's how I simplify and fix the error:
var input = [[1, 2, 3, 4],
[5, 6, 7, 8],
[9, 10, 11, 12],
[13, 14, 15, 16]];
var spiralTraversal = function(matriks){
var result = [];
var goAround = function(matrix) {
if (matrix.length == 0) {
return;
}
// right
result = result.concat(matrix.shift());
// down
for (var j=1; j < matrix.length - 1; j++) {
result.push(matrix[j].pop());
}
// bottom
result = result.concat(matrix.pop().reverse());
// up
for (var k=matrix.length -2; k > 0; k--) {
result.push(matrix[k].shift());
}
return goAround(matrix);
};
goAround(matriks);
return result;
};
var result = spiralTraversal(input);
console.log('result', result);
Running it outputs:
result [1, 2, 3, 4, 12, 16, 15, 14, 13, 5, 6, 7, 8, 11, 10, 9]
JSFiddle: http://jsfiddle.net/eb34fu5z/
Important things:
-
concat
on Array returns the result - it's notresult = result.concat(otherArray)
so you need to store the resultconcat
like this:result = result.concat(otherArray)
- check the termination condition at the top of the recursive array
- for each pass do as expected (top, right, bottom, left)
- return the result
This is how I would do it, but I would add error checking to make sure the array has the same number of "rows" and "columns". So, assuming the input is valid, here we go:
var input = [[1, 2, 3, 4],
[5, 6, 7, 8],
[9, 10, 11, 12],
[13, 14, 15, 16]];
function run(input, result) {
if (input.length == 0) {
return result;
}
// add the first row to result
result = result.concat(input.shift());
// add the last element of each remaining row
input.forEach(function(rightEnd) {
result.push(rightEnd.pop());
});
// add the last row in reverse order
result = result.concat(input.pop().reverse());
// add the first element in each remaining row (going upwards)
var tmp = [];
input.forEach(function(leftEnd) {
tmp.push(leftEnd.shift());
});
result = result.concat(tmp.reverse());
return run(input, result);
}
var result = run(input, []);
console.log('result', result);
What conclusions:
result [1, 2, 3, 4, 8, 12, 16, 15, 14, 13, 9, 5, 6, 7, 11, 10]
The general idea is that we know that for each pass we need to do the following:
- Add the first array to the input
- Add the last element from each remaining array in the input
- Add the last array in the input
- Add the first element from each remaining array as input
This way, if we do recursion, doing this on each pass, we can do the spiral.
JSFiddle: http://jsfiddle.net/2v6k5uhd/
+9
source to share
This is a solution for any matrix (m * n), not just a square (m * m). The example below takes a 5 * 4 matrix and prints in a spiral format.
var matrix = [[1,2,3,4], [14,15,16,5], [13,20,17,6], [12,19,18,7], [11,10,9,8]];
var row = currentRow = matrix.length, column = currentColumn = matrix[0].length;
while(currentRow > row/2 ){
// traverse row forward
for(var i = (column - currentColumn); i < currentColumn ; i++) { console.log(matrix[row - currentRow][i]); }
// traverse column downward
for(var i = (row - currentRow + 1); i < currentRow ; i++) { console.log(matrix[i][currentColumn - 1]) }
// traverse row backward
for(var i = currentColumn - 1; i > (column - currentColumn) ; i--) { console.log(matrix[currentRow - 1][i - 1]); }
// traverse column upward
for(var i = currentRow - 1; i > (row - currentRow + 1) ; i--) { console.log(matrix[i - 1][column - currentColumn]) }
currentRow--;
currentColumn--;
}
+5
source to share
Your algorithm seems fine, there is only one mistake. There are several things, some of which are difficult to detect than others.
-
concat
the method does not modify the array (for example,push
does), but returns a new array that contains all the elements from the original array and arguments.result
does not mutate.To fix this, you can either
- use
result = result.concat(…);
- make it an explicit loop where you do
result.push(…)
(like previous, left and previous) or - use to push multiple values at the same time.
result.push.apply(result, …)
- use
- Your "left" or "up" loop skips one element, and the bottom one. Either when you walk to the left, you need to go to the first element (use the condition
>= 0
in the condition), or when you walk, you will need to start with the last, not the second-last line (matrix.length-1
) - In the loop that shrinks the matrix for the next iteration, you forgot the last row, it should be
for (var i=0; i < temp.length; i++)
(nottemp.length-1
). Otherwise, you will get very unfortunate results. - In your base case, it should be 0 (and 1), not (1 and) 2. This will simplify your script and avoid errors (in extreme cases).
- You expect your matrices to be square, but they can be rectangular (or even have lines of irregular length). Access to
.length
may not be what you expect - better double-tagged and error with descriptive message. - Both
spiralTraversal
andgoAround
are not operatorreturn
of (recursive) call. They just fillresult
in but don't return anything.
+4
source to share
Recursive solution:
Instead of going in a circle, I simply iterate over the top row and rightmost column, and then recursively call the function on the "reversed" matrix.
var input = [
[ 1, 2, 3, 4],
[ 5, 6, 7, 8],
[ 9,10,11,12],
[13,14,15,16]
];
let spiral = (mat) => {
if(mat.length && mat[0].length) {
mat[0].forEach(entry => { console.log(entry)})
mat.shift();
mat.forEach(item => {
console.log(item.pop())
});
spiral(reverseMatrix(mat))
}
return;
}
let reverseMatrix = (mat) => {
mat.forEach(item => {
item.reverse()
});
mat.reverse();
return mat;
}
console.log("Clockwise Order is:")
spiral(input)
+2
source to share
Here's my function:
let array_masalah = [
[1,2,3,4],
[5,6,7,8],
[9, 10, 11, 12],
[13, 14, 15,16],
];
let array_masalah_2 = [
[1, 2, 3, 4, 5],
[6, 7, 8, 9, 10],
[11, 12, 13, 14, 15],
[16, 17, 18, 19, 20],
];
function polaSpiral(array_masalah) {
function spiral(array) {
if (array.length == 1) {
return array[0];
}
var firstRow = array[0]
, numRows = array.length
, nextMatrix = []
, newRow
, rowIdx
, colIdx = array[1].length - 1
for (colIdx; colIdx >= 0; colIdx--) {
newRow = [];
for (rowIdx = 1; rowIdx < numRows; rowIdx++) {
newRow.push(array[rowIdx][colIdx]);
}
nextMatrix.push(newRow);
}
firstRow.push.apply(firstRow, spiral(nextMatrix));
return firstRow
}
console.log(spiral(array_masalah));
}
polaSpiral(array_masalah) // [ 1, 2, 3, 4, 8, 12, 16, 15, 14, 13, 9, 5, 6, 7, 11, 10 ]
polaSpiral(array_masalah_2) // [ 1, 2, 3, 4, 5, 10, 15, 20, 19, 18, 17, 16, 11, 6, 7, 8, 9, 14, 13, 12 ]
+2
source to share
While not recursive, it at least outputs the correct answer:
result: [ 1, 2, 3, 4, 8, 12, 16, 15, 14, 13, 9, 5, 6, 7, 11, 10 ]
I would say that the only strange thing about this is to "reset" the variables i, j after each while loop. Also, maybe a cleaner recursive solution.
var array = [
[1, 2, 3, 4],
[5, 6, 7, 8],
[9, 10, 11, 12],
[13, 14, 15, 16]
];
function spiralTraversal(array) {
let discovered = new Set();
let result = [];
let totalSpots = array.length * array[0].length;
let direction = 'right';
for (var i = 0; i < array.length; i ++) {
for (var j = 0; j < array[i].length; j++) {
while (totalSpots) {
while (direction === 'right' && !!bounds(array, i, j) && !discovered.has(array[i][j])) {
discovered.add(array[i][j]);
result.push(array[i][j]);
totalSpots--;
j++;
}
direction = 'down';
i++;
j--;
while (direction === 'down' && !!bounds(array,i, j) && !discovered.has(array[i][i])) {
discovered.add(array[i][j]);
result.push(array[i][j]);
totalSpots--;
i++;
}
direction = 'left';
j--;
i--;
while (direction === 'left' && !!bounds(array, i, j) && !discovered.has(array[i][j])) {
discovered.add(array[i][j]);
result.push(array[i][j]);
totalSpots--;
j--;
}
direction = 'up';
i--;
j++
while (direction === 'up' && bounds(array, i, j) && !discovered.has(array[i][j])) {
discovered.add(array[i][j]);
result.push(array[i][j]);
totalSpots--;
i--;
}
direction = 'right';
j++;
i++;
}
}
}
return result;
}
function bounds(array, i, j){
if (i < array.length && i >= 0 && j < array[0].length && j >= 0) {
return true;
} else {
return false;
}
};
+1
source to share
const spiralOrder = matrix => {
if (!matrix || matrix.length === 0) {
return [];
}
let startRow = 0;
let startCol = 0;
let ans = [];
let endCol = matrix[0].length - 1;
let endRow = matrix.length - 1;
while (startRow <= endRow && startCol <= endCol) {
for (let i = startCol; i <= endCol; i++) {
ans.push(matrix[startRow][i]);
}
startRow++;
for (let i = startRow; i <= endRow; i++) {
ans.push(matrix[i][endCol]);
}
endCol--;
if (startRow <= endRow) {
for (let i = endCol; i >= startCol; i--) {
ans.push(matrix[endRow][i]);
}
endRow--;
}
if (startCol <= endCol) {
for (let i = endRow; i >= startRow; i--) {
ans.push(matrix[i][startCol]);
}
startCol++;
}
}
return ans;
};
let input = [[1, 2, 3], [4, 5, 6], [7, 8, 9]];
//Output: [1, 2, 3, 6, 9, 8, 7, 4, 5];
spiralOrder(input);
+1
source to share
I am using C #:
public static IList<int> spiralTraversal (int[,] matrix)
{
IList<int> list = new List<int>();
// Get all bounds before looping.
int bound0 = matrix.GetUpperBound(0);
int bound1 = matrix.GetUpperBound(1);
int totalElem = (bound0+1) * (bound1+1);
int auxbound0 = 0;
int auxbound1 = 0;
string direction = "left";
int leftCtrl = 0;
int rightCtrl = 0;
int upCtrl = 0;
int downCtrl = 0;
for (int i=0;i< totalElem;i++)
{
if (direction == "down")
{
list.Add(matrix[auxbound0, auxbound1]);
if (auxbound0 == bound0 - downCtrl)
{
direction = "right";
auxbound1 -= 1;
downCtrl += 1;
continue;
}
else
{
auxbound0 += 1;
}
}
if (direction == "left")
{
list.Add(matrix[auxbound0, auxbound1]);
if (auxbound1 == bound1 - leftCtrl)
{
direction = "down";
auxbound0 += 1;
leftCtrl += 1;
continue;
}
else
{
auxbound1 += 1;
}
}
if (direction == "up")
{
list.Add(matrix[auxbound0, auxbound1]);
if (auxbound0 == 1 + upCtrl)
{
direction = "left";
auxbound1 += 1;
upCtrl += 1;
continue;
}
else
{
auxbound0 -= 1;
}
}
if (direction == "right")
{
list.Add(matrix[auxbound0, auxbound1]);
if (auxbound1 == rightCtrl)
{
direction = "up";
auxbound0 -= 1;
rightCtrl += 1;
continue;
}
else
{
auxbound1 -= 1;
}
}
}
return list;
}
0
source to share
Below is a Javascript solution. I've added comments to the code so you can follow the process :)
var array = [
[1, 2, 3, 4],
[5, 6, 7, 8],
[9, 10, 11, 12],
[13, 14, 15, 16]
];
var n = array.length;
//create empty 2d array
var startRow = 0;
var endRow = n - 1;
var startColumn = 0;
var endColumn = n - 1
var newArray = [];
// While loop is used to spiral into the 2d array.
while(startRow <= endRow && startColumn <= endColumn) {
// Reading top row, from left to right
for(var i = startColumn; i <= endColumn; i++) {
newArray.push(array[startColumn][i]);
}
startRow++; // Top row read.
// Reading right column from top right to bottom right
for(var i = startRow; i <= endRow; i++) {
newArray.push(array[i][endColumn]);
}
endColumn--; // Right column read
// Reading bottom row, from bottom right to bottom left
for(var i = endColumn; i >= startColumn; i--) {
newArray.push(array[endRow][i]);
}
endRow--; // Bottom row read
// Reading left column, from bottom left to top left
for(var i = endRow; i >= startRow; i--) {
newArray.push(array[i][startColumn]);
}
startColumn++; // left column now read.
} // While loop will now spiral in the matrix.
console.log(newArray);
:)
0
source to share
This solution takes a spiral array and converts it to an ordered array .
It sorts the spiral matrix in top, right, bottom, left format.
const matrix = [
[1, 2, 3, 4, 5],
[16, 17, 18, 19, 6],
[15, 24, 25, 20, 7],
[14, 23, 22, 21, 8],
[13, 12, 11, 10, 9],
];
function getOrderdMatrix(matrix, OrderdCorner) {
// If the Matrix is 0 return the OrderdCorner
if (matrix.length > 0) {
//Pushes the top of the matrix to OrderdCorner array
OrderdCorner.push(...matrix.shift());
let left = [];
/*Pushes right elements to the Orderdcorner array and
Add the left elements to the left array */
for (let i = 0; i < matrix.length; i++) {
OrderdCorner.push(matrix[i][matrix[i].length - 1])
matrix[i].pop(); //Remove Right element
if (matrix[i].length > 0) {
//Starts from the last element of the left corner
left.push(matrix[(matrix.length - 1) - i][0])
matrix[(matrix.length - 1) - i].shift();
}
}
/* If the array length is grater than 0 add the bottom
to the OrderdCorner array */
if (matrix.length > 0) {
OrderdCorner.push(...matrix.pop().reverse());
}
//Ads the left array to the OrderdCorner array
OrderdCorner.push(...left);
return getOrderdMatrix(matrix, OrderdCorner);
} else {
return OrderdCorner
}
}
console.log(getOrderdMatrix(matrix,[]));
Returns [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25]
0
source to share
Here's the custom version:
function spiral(n) {
// Create 2D array of size n*n
var matrix = new Array(n);
for(var i=0; i < matrix.length; i++) {
matrix[i] = new Array(n);
}
for(var i=0; i < n;i++) {
for(var j=0; j < n; j++) {
matrix[i][j] = 0;
}
}
var startNum = 0;
var rowNum = 0;
function spin(rowNum) {
// right
for(var j=rowNum; j < (n-rowNum); j++) {
startNum++;
matrix[rowNum][j] = startNum;
}
if(startNum === (n*n)) {
return; // exit if number matches to the size of the matrix. ( 16 = 4*4 )
}
// down
for(var i=(rowNum+1); i < (n-(rowNum+1)); i++) {
startNum++;
matrix[i][n-(rowNum+1)] = startNum;
}
if(startNum === (n*n)) {
return; // exit if number matches to the size of the matrix. ( 16 = 4*4 )
}
// left
for(var j=(n-(1+rowNum)); j >= rowNum; j--) {
startNum++;
matrix[(n-(1+rowNum))][j] = startNum;
}
if(startNum === (n*n)) {
return; // exit if number matches to the size of the matrix. ( 16 = 4*4 )
}
//top
for(var i=(n-(2+rowNum)); i > rowNum; i--) {
startNum++;
matrix[i][rowNum] = startNum;
}
if(startNum === (n*n)) {
return; // exit if number matches to the size of the matrix. ( 16 = 4*4 )
}
spin(rowNum+1);
}
spin(rowNum);
console.log(matrix)
}
spiral(6);
0
source to share