Spiral traversal of a matrix - recursive solution in JavaScript

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 the concat 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:

  1. Add the first array in input
  2. Add the last item from each remaining array in input
  3. Add the last array in input
  4. 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/


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--;
}

Your algorithm seems fine, there is only one mistake There are a few things, some more hard to spot than others.

  1. The concat method does not alter the array (like push does), but returns a new array that contains all the elements from the original array and the arguments. The result 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
  2. 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)
  3. 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++) (not temp.length-1). Otherwise you get very unfortunate results.
  4. Your base case should be 0 (and 1), not (1 and) 2. This will both simplify your script and avoid errors (in edge cases).
  5. 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.
  6. Both spiralTraversal and goAround are missing a return statement for the (recursive) call. They just fill up result but don't return anything.

🌀 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;
}