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

The essence of the spiral order traversal algorithm for matrices lies in navigating through the matrix in a spiral pattern—initially moving left-to-right, then top-to-bottom, followed by right-to-left, and finally bottom-to-top, with this cycle repeating until all elements have been visited. The algorithm employs a direction variable to control the traversal direction, which alternates between positive and negative values to switch between these four directions.

Now, let’s look at the workflow of the implementation:

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: