Last updated: Nov 26, 2022
Difficulty : medium
Runtime : 103 ms Faster than 23.84 %
Memory : 41.7 mb Lesser than 72.06 %

54. Spiral Matrix - javascript solution

Given an m x n matrix, return all elements of the matrix in spiral order.

Example 1: Input: matrix = [[1,2,3],[4,5,6],[7,8,9]] Output: [1,2,3,6,9,8,7,4,5]

Example 2: Input: matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]] Output: [1,2,3,4,8,12,11,10,9,5,6,7]

Constraints:

  • m == matrix.length
  • n == matrix[i].length
  • 1 <= m, n <= 10
  • -100 <= matrix[i][j] <= 100

Solution:

/**
 * @param {number[][]} matrix
 * @return {number[]}
 */

var spiralLoop = function (matrix, result) {
  if (!matrix.length) {
    return result;
  }
  result.push(...matrix.shift());
  var l = 0;
  while (l < matrix.length && matrix[l].length > 0) {
    if (l === matrix.length - 1) {
      while (matrix[l].length > 0) {
        result.push(matrix[l].pop());
      }
      matrix.pop();
    } else {
      result.push(matrix[l].pop());
    }
    l++;
  }
  // reverse order and recursion
  if (matrix.length > 0) {
    var i = matrix.length - 1;
    while (i >= 0 && matrix[i].length > 0) {
      result.push(matrix[i].shift());
      i--;
    }
    spiralLoop(matrix, result);
  }
  return result;
};

var spiralOrder = function (matrix) {
  return spiralLoop(matrix, []);
};

Explanation:

This problem requires you to create an algorithm that returns the matrix in spiral order. To understand the solution above let's first understand what is a matrix. A matrix has columns and rows and starting from the first row you have to move to the last column and then cover the last row in reverse order until you reach back to the row below the first row.

I have used two accessor functions in this algorithm. The first is the shift and the second is pop. With the help of a while loop, it is easy to iterate over the rows and columns. The algorithm keeps removing the first or last item based on the spiral order and stores it in the result variable passed as an argument to the spiralLoop function. Finally, if the matrix still has rows and columns a recursive call is made to this spiralLoop function.

Let's understand what is going on in the algorithm at each step. On line 6, create a spiralLoop function and pass the matrix and result as parameters. On line 7, if the matrix has no elements then an empty array will be returned which is held by the result variable as a default parameter.

On line 10, instead of running a while loop, what we can do is spread the first row into the result. This reduces the iteration that we need to do for the first row as we need to move straight until we reach the last element.

On line 12, we use a while loop to iterate over the columns of the matrix and keep removing the last element of every row until we reach the last row of the matrix. Remember, We need to make sure that we run the while loop only if the row that we are iterating over has elements inside it. Otherwise, it will return undefined, hence, the condition matrix[l].length > 0 is used on line 12.

The first loop ends at line 22 but until here we have only reached the last row and also moved to its starting element. We still need to move back to the row below the first row and to do this we need to make sure that there are rows available with an if condition.

On line 26, we run a while loop again if there are rows available. We need to keep removing the first element of each row instead of the last element until we reach the beginning. At the end of this loop, we have covered the outermost spiral order but are still left with a sub-matrix if there are more than two columns.

On line 30, we do a recursive call to the spiralLoop function to start the process again. Finally, the algorithm will cover all the rows and columns that are left.