Spiral Matrix

mediumFREEMath & GeometryBlind 75

Given an m x n matrix, return all elements in spiral order as a list.

The tests print the returned list space-separated.

Example

Input

1,2,3
4,5,6
7,8,9

Output

1 2 3 6 9 8 7 4 5

Reasoning

The input is a $3 \times 3$ grid written row by row: 1,2,3 is the top row, 4,5,6 the middle row and 7,8,9 the bottom row. Spiral order walks the outer border clockwise from the top-left corner, then repeats on whatever is left inside.
Outer ring: the top edge, left to right, gives 1, 2, 3. The right edge going down adds 6, 9. The bottom edge, right to left, adds 8, 7. The left edge going up adds only 4, because 7 and 1 are corners already visited.
That ring covers $3 + 2 + 2 + 1 = 8$ cells, each exactly once.
What remains is a $1 \times 1$ inner grid holding 5, which comes last: 1 2 3 6 9 8 7 4 5.
Notice that for a non-square grid the inner remainder can be a single row: the $3 \times 4$ test finishes its outer ring at 5 and then reads the leftover row 6, 7 left to right.

Constraints

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

More from Blind 75

Alien Dictionaryhard Clone Graphmedium Combination Summedium Word Search IIhard Merge K Sorted Listshard

Concept primer

Background Knowledge

The Spiral Matrix problem involves traversing a 2D matrix in a spiral order, which means starting from the top-left corner and moving in a clockwise direction. To understand this problem, it's essential to have a good grasp of matrix operations and array indexing. In a 2D matrix, each element is identified by its row and column index, typically represented as (i, j), where i is the row index and j is the column index.

The concept of spiral order is crucial in this problem. It involves traversing the matrix in a specific pattern, where we move right, then down, then left, and finally up, repeating this process until all elements are visited. This pattern requires careful management of the matrix boundaries and the current position. Understanding how to update the boundaries and the current position is vital to solving this problem.

To tackle this problem, it's also helpful to have experience with looping constructs, such as for loops or while loops, and conditional statements, like if statements. These constructs will be used to control the flow of the traversal and to handle the different directions of the spiral.

Algorithm/Approach

The general approach to solving the Spiral Matrix problem involves using a boundary-based approach. This means we'll maintain four boundaries: top, bottom, left, and right, which represent the current limits of the matrix. We'll then use a loop to traverse the matrix in a spiral order, updating the boundaries and the current position at each step.

Step-by-Step Strategy

To implement the solution, follow these steps:

Initialize the boundaries: top, bottom, left, and right to the edges of the matrix.
Traverse the matrix in a spiral order by moving right, then down, then left, and finally up.
At each step, update the boundaries and the current position.
Use conditional statements to handle the different directions of the spiral and to check if all elements have been visited.

Common Pitfalls

When implementing the solution, watch out for:

Incorrectly updating the boundaries, which can lead to missing elements or visiting elements multiple times.
Failing to handle the different directions of the spiral, which can result in an incorrect traversal order.
Not checking if all elements have been visited, which can lead to an infinite loop.

Time & Space Complexity

The expected time complexity for this problem is $O(m \cdot n)$ , where m is the number of rows and n is the number of columns in the matrix. This is because we need to visit each element in the matrix once. The expected space complexity is $O(m \cdot n)$ as well, as we need to store the result of the spiral traversal. However, if we're only required to print the elements in spiral order, the space complexity can be reduced to $O(1)$ , excluding the space needed for the output.

solution.py

Python 3.13

Test results