Spiral traversal of a matrix - recursive solution in JavaScript
Solution 1
Your code is very close but it is doing more than it needs to do. Here I simplify and bug fix:
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 does not mutate the caller so you need to save the result of theconcat
like so:result = result.concat(otherArray)
- check the terminating condition at top of recursive array
- for each pass, do the expected (top, right, bottom, left)
- return the result
Here is how I would do it but I would add error checking to verify the array has an equal 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);
Which outputs:
result [1, 2, 3, 4, 8, 12, 16, 15, 14, 13, 9, 5, 6, 7, 11, 10]
The general idea is we know for each pass we need to do these things:
- Add the first array in input
- Add the last item from each remaining array in input
- Add the last array in input
- Add the first item from each remaining array in input
So if we do the recursion with doing that at each pass, we can accomplish the spiraling.
JSFiddle: http://jsfiddle.net/2v6k5uhd/
Solution 2
🌀 Spiral Array (ES6)
ES6 allows us to keep it simple:
function spiral(matrix) {
const arr = [];
while (matrix.length) {
arr.push(
...matrix.shift(),
...matrix.map(a => a.pop()),
...(matrix.pop() || []).reverse(),
...matrix.map(a => a.shift()).reverse()
);
}
return arr;
}
Solution 3
This solution is for any kind of matrix (m * n), not just square(m * m). Below example takes 5*4 matrix and prints in 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--;
}
Solution 4
Your algorithm seems fine, there is only one mistake There are a few things, some more hard to spot than others.
-
The
concat
method does not alter the array (likepush
does), but returns a new array that contains all the elements from the original array and the arguments. Theresult
is not mutated.To fix this, you could either
- use
result = result.concat(…);
- make it an explicit loop where you do
result.push(…)
(like the down, left and up ones you already wrote) or - use
result.push.apply(result, …)
to push multiple values at once
- use
- Your "left" or "up" loop does miss one element, the bottom left one. Either when going left, you need advance to the first element (use
>= 0
in the condition), or when going up you will need to start in the last instead of the second-to-last row (matrix.length-1
) - In the loop that shrinks the matrix for the next iteration you forgot the last row, it needs to be
for (var i=0; i < temp.length; i++)
(nottemp.length-1
). Otherwise you get very unfortunate results. - Your base case should be 0 (and 1), not (1 and) 2. This will both simplify your script and avoid errors (in edge cases).
- You expect your matrices to be square, but they could be rectangular (or even have lines of uneven length). The
.length
you are accessing might be not the one you expect - better doublecheck and throw an error with a descriptive message. - Both
spiralTraversal
andgoAround
are missing areturn
statement for the (recursive) call. They just fill upresult
but don't return anything.
Solution 5
Recursive Solution:
Instead of going around, I just go over the top row, and the rightmost column, 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)
Comments
-
zahabba almost 2 years
I'm trying to come up with a solution that takes in a matrix like this:
[[1,2,3,4], [5,6,7,8], [9,10,11,12], [13,14,15,16]]
and returns an array traversing the array as 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, in which 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 reforms the array without that outer "shell" so that it can be recursively called on what's left until there's an array of one element in the center or a 2x2 matrix (my base cases, although the latter might not be necessary...)
My solution, which doesn't work, is as follows. 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); };
-
zahabba almost 9 yearsThank you. I made the first suggested change but I'm still getting an error. jsfiddle.net/vdn9ygae
-
Bergi almost 9 years@zahabba: OK, I looked more closely and found a few more things :-)
-
wnull over 5 yearsTell me, is it possible to implement this in PHP?
-
Ananda over 5 years@Lior Elrom the code is crisp and concise. Never thought spread operator can be used for this task.
-
Matan Tubul over 5 yearsthere is "undefined" exception if you try it on matrix size N*M (5*4) for example. surround the loop with try and catch are solving that. anyway this is beautiful solution.
-
Lior Elrom over 5 years@MatanTubul good point. Instead of using try catch, replace
...matrix.pop().reverse()
with...(matrix.pop() || []).reverse()
to account for non-array result. -
Sceat over 3 years@LiorElrom
...matrix.pop()?.reverse?.() ?? []
-
Lior Elrom over 3 years@Sceat Nice! 👍
-
Scott Sauyet about 3 yearsNote also what I think of as a simpler answer to a similar question.
-
jajabarr over 2 yearsThis code looks clean and fancy, but it's not performant. Anyone else looking at this, move down below to the simple (4) forloop solutions where it's actually O(M*N). Ignore any solution that contains
.reverse()