Solution: Spiral Matrix

Statement#

Given an $m\times n$ matrix, return an array containing the matrix elements in spiral order, starting from the top-left cell.

Constraints:

• $1\leq$ matrix.length $\leq 10$
• $1\leq$ matrix[i].length $\leq 10$
• $-100\leq$ matrix[i][j] $\leq 100$

Solution#

We’ll maintain a variable, direction, which indicates the direction we need to travel in. It will store the value of either $1$ or $-1$. Its value will change based on the following rules:

• It will be $1$ if we’re traveling in the following directions:

  • Left to right (horizontal)
  • Top to bottom (vertical)

• It will be $-1$ if we’re traveling in the following directions:

  • Right to left (horizontal)
  • Bottom to top (vertical)

Here’s how the algorithm works:

1. We initialize the following variables:

   • rows, cols = len(matrix), len(matrix[0]): These are the total number of rows and columns in the matrix, respectively.
   • row, col = 0, -1: These are the pointers used to traverse the matrix.
   • direction = 1: This indicates the direction we need to travel in. It is initialized to $1$ since our first traversal will be in the left to right (horizontal) direction.
   • result = []: This array stores the matrix elements in spiral order.

2. We start the traversal from the top left cell in the matrix:

   1. We first travel from left to right in a row by adding the direction variable to col while keeping the value of row unchanged. At each iteration, we will add matrix[row][col] to result. At the end of this row traversal, we decrement rows by $1$ because if we traverse a column after this, we’ll traverse one less element.
   2. Next, we travel from top to bottom in a column by adding the direction variable to row while keeping the value of col unchanged. At each iteration, we will add matrix[row][col] to result. At the end of this column traversal, we decrement cols by $1$ because if we traverse a row after this, we’ll traverse one less element.

3. We reverse the direction by multiplying the direction variable by $-1$:

   1. Now, we travel from right to left in a row by adding the direction variable (which is now $-1$) to col while keeping the value of row unchanged. At each iteration, we will add matrix[row][col] to result. At the end of this row traversal, we decrement rows by $1$ because if we traverse a column after this, we’ll traverse one less element.

   2. Next, we travel from bottom to top in a col by adding the direction variable (which is now $-1$) to row while keeping the value of col unchanged. At each iteration, we will add matrix[row][col] to result. At the end of this column traversal, we decrement cols by $1$ because if we traverse a row after this, we’ll traverse one less element.

4. We again reverse the direction by multiplying the direction variable by $-1$.

5. The four steps above are repeated until all the cells of the matrix have been traversed, after which result stores the spiral order, so we return result.

Let’s look at the following illustration to get a better understanding of the solution:

Let’s have a look at the code for the algorithm we just discussed:

Time complexity#

The time complexity of this solution is $O(m \times n)$ since each cell of the matrix is traversed.

Space complexity#

The space complexity of this solution is $O(1)$ since no extra space is used.