Spiral Matrix

Mark as Completed

Lesson

Given a 2D matrix, return all elements of the matrix in spiral order. Implement a function called spiralOrder(matrix)
that takes in a 2D matrix as input and returns an array of the matrix elements in spiral order.

Spiral order refers to the order in which the elements of a 2D matrix are traversed in a spiral pattern, starting from the top-left corner and moving towards the right, then downwards, then towards the left, and finally upwards. The pattern is repeated until all elements in the matrix have been traversed. So, the traversal follows a spiral pattern resembling a spiral shape, hence the name spiral order.

Let's say we have the following 2D matrix:

1  2  3  4
5  6  7  8
9  10 11 12
13 14 15 16

To traverse this matrix in spiral order, we start at the top left corner and visit each element in a clockwise spiral pattern, so the order of traversal would be:

1  2  3  4  8  12 16 15 14 13 9 5 6 7 11 10

We start at 1, then move right to 2, 3, and 4. Then, we move down to 8, 12, 16, and then left to 15, 14, 13. Next, we move up to 9, 5, and 6, then right to 7 and finally, down to 11 and 10 to complete the traversal.

Solution Walkthrough

Solution Code

function spiralOrder(matrix) {
  const result = [];

  if (matrix.length === 0) {
    return result;
  }

  // define boundaries
  let top = 0, bottom = matrix.length - 1, left = 0, right = matrix[0].length - 1;

  while (top <= bottom && left <= right) {
    // traverse top row from left to right
    for (let i = left; i <= right; i++) {
      result.push(matrix[top][i]);
    }
    top++;

    // traverse right column from top to bottom
    for (let i = top; i <= bottom; i++) {
      result.push(matrix[i][right]);
    }
    right--;

    // traverse bottom row from right to left
    if (top <= bottom) {
      for (let i = right; i >= left; i--) {
        result.push(matrix[bottom][i]);
      }
      bottom--;
    }

    // traverse left column from bottom to top
    if (left <= right) {
      for (let i = bottom; i >= top; i--) {
        result.push(matrix[i][left]);
      }
      left++;
    }
  }

  return result;
}

We will start by initializing an empty array result
that will hold all the matrix elements in spiral order. Then we will check for the edge case of an empty matrix, in which case we return an empty result array.After that, we will define the boundaries of the matrix using four variables top
, bottom
, left
, and right
. top
will initially be 0, bottom
will initially be the last row of the matrix, left
will initially be 0, and right
will initially be the last column of the matrix.Next, we will use a while loop to traverse the matrix in spiral order. We will do this as long as top
is less than or equal to bottom
and left
is less than or equal to right
. Within the while loop, we will perform the following four steps in order:

Traverse the top row from left to right and add the elements to result
. Increase top
by 1.
Traverse the right column from top to bottom and add the elements to result
. Decrease right
by 1.
Traverse the bottom row from right to left and add the elements to result
. Decrease bottom
by 1.
Traverse the left column from bottom to top and add the elements to result
. Increase left
by 1.

We will continue to perform these four steps until we have added all the elements in the matrix to result
in spiral order.Finally, we return the result
array containing all the matrix elements in spiral order.Big O Complexity Analysis: The time complexity of this solution is O(mn), where m
is the number of rows and n
is the number of columns in the matrix. This is because we need to traverse every element in the matrix to add it to result
in spiral order.The space complexity of this solution is O(mn), where m
is the number of rows and n
is the number of columns in the matrix. This is because we need to store all the elements in the matrix in the result
array.

Previous Lesson Next Lesson