Spiral traversal of a matrix - recursive solution in JavaScript

Question

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

Answer 1

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

Answer 2

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/

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

Answer 4

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.

Answer 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)

Answer 6

Here 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 ]

Answer 7

While not recursive, it at least outputs the correct answer of:

result: [ 1, 2, 3, 4, 8, 12, 16, 15, 14, 13, 9, 5, 6, 7, 11, 10 ]

I'd say the only weird thing about this is having to "reset" the variables i,j after each while loop. Also, there's probably 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;
  }
};

Answer 8

Below is a Javascript solution. I have added comments to the code so you can follow along with 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);

:)

Answer 9

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

Answer 10

ES6 JS version with clockwise and anticlockwise spiral traversal.

function traverseSpiral(arr2d,directionMap,initialPos){
  // Initializing length.
  const len = arr2d.length;
  let totalElementsTraversed =0;
  // Elements in the first line is equal to the array length.
  // (as this is a square matrix)
  let elementsInLine=len;
  let elementsTraversedInRow = 0;
  let linesCompleted = 1;
  let direction = initialPos[0] === 0 ? 'r' : 'd';
  // Function to move in the desired direction.
  const move = checkDirectionAndMove(initialPos);
  const spiralArray = [];
  while( totalElementsTraversed!==len*len){
    // On Each line completion
    if(elementsTraversedInRow===elementsInLine){
      linesCompleted++;
      // Reset elements traversed in the row.
      elementsTraversedInRow =0;
      // After each line completion change direction.
      direction = directionMap.get(direction);
      // For every 2 traversed lines elements in the line will decrease.
      if(linesCompleted % 2===0) elementsInLine--;
    }
    // Update elements traversed
    totalElementsTraversed+=1
    elementsTraversedInRow+=1;
    // Move in the defined direction
    const [ down,right] = move(direction);
    spiralArray.push(arr2d[down][right]);
    
  }
  return spiralArray;
}

function checkDirectionAndMove(initialPosition) {
  // Unpack array to variables
  let [down,right] = initialPosition;
  // Return function.
  return (direction)=> {
    // Switch based on right/left/up/down direction.
    switch(direction){
      case 'r':
        right++;
        break;
      case 'l':
        right--; 
        break;
      case 'd':
        down++;
        break;
      default :
        down--;
    }
    return [down,right]
  }
}
// If current direction is right move down and so on....
const clockWiseMap = new Map(Object.entries({
  'r':'d',
  'd':'l',
  'l':'u',
  'u':'r'
}));
// If current direction is right move up and so on....
const antiClockWiseMap = new Map(Object.entries({
  'r':'u',
  'd':'r',
  'l':'d',
  'u':'l'
}));
// Spiral traversal in the clockwise direction.
const clockWiseSpiralTraversal = traverseSpiral( 
  [[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]],
  clockWiseMap,
  [0,-1]
)
// Spiral traversal in the anti-clockwise direction.
const antiClockWiseSpiralTraversal = traverseSpiral( 
  [[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]],
  antiClockWiseMap,
  [-1,0]
)
console.log("Clock wise traversal :", clockWiseSpiralTraversal)
console.log("Anti-clock wise traversal :",antiClockWiseSpiralTraversal)

Returns :

Clock wise traversal : [ 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 ]

Anti-clock wise traversal : [ 1, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 17, 24, 23, 22, 21, 20, 19, 18, 25 ]

Main used techniques and others: Closure, Arrow functions, Higher-order functions, Conditional/ternary operator, Array destructuring, and JS map.

Answer 11

This is my solution with loops only and without methods:

function spiral(n) {
  const matrix = [];
  for (let i = 0; i < n; i++) matrix[i] = [];

  let [row, col, phase, num] = [0, 0, 0, 1];

  while (num <= n ** 2) {
    // to right
    for (; col < n - phase; col++) matrix[row][col] = num++;
    // down
    for (; row < n - phase - 1; row++) matrix[row + 1][col - 1] = num++;
    // to left
    for (; col > phase + 1; col--) matrix[row][col - 2] = num++;
    // up
    for (; row > phase + 1; row--) matrix[row - 1][col - 1] = num++;
    phase++;
  }
  return matrix;
}

Answer 12

I'm use to 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;
    }

Answer 13

This solution takes spiral array and converts it to Ordered Array.

It Sorts Spiral Matrix with the format of Top, Right, Bottom, Left.

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]

Answer 14

Here's a configurable 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);

Example : https://jsfiddle.net/dino_myte/276ou5kb/1/

Answer 15

I have written an article for a while about this beautiful toy problem, I really enjoy it. you might need to check out my solution.

you can follow me on Medium and you can check my article from here.

var spiralTraversal = function (matrix, result = []) {
  // TODO: Implement me!

  //  if the length of the matrix ==0 we will return the result
  if (matrix.length == 0) {
    return result;
  }
  // we need to push the elements inside the first element of the array then delete this element
  while (matrix[0].length) {
    result.push(matrix[0].shift());
  }
  //top right to bottom right
  matrix.forEach((row) => {
    result.push(row.pop());
  });
  //bottom right to bottom left
  while (matrix[matrix.length - 1].length) {
    result.push(matrix[matrix.length - 1].pop());
  }
  //reverse again so we can retraverse on the next iteration
  matrix.reverse();
  //filter out any empty arrays
  matrix = matrix.filter((element) => element.length);

  //recursive case
  result = spiralTraversal(matrix, result);

  //return the result and filter any undefined elements
  return result.filter((element) => element);
};