Problem Description

You need to create a square matrix of size n x n and fill it with numbers from 1 to n² following a spiral pattern.

The spiral pattern means you start filling from the top-left corner and move:

• First, go right across the first row
• Then, go down along the last column
• Then, go left across the bottom row
• Then, go up along the first column
• Continue this spiral pattern inward until all positions are filled

For example, if n = 3, you would create a 3x3 matrix and fill it with numbers 1 through 9 in spiral order:

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

The filling path would be: start at position (0,0) with 1, move right to fill 2 and 3, then move down to fill 4 and 5, then move left to fill 6 and 7, then move up to fill 8, and finally move right to fill 9.

The solution uses a simulation approach with direction vectors. The dirs tuple (0, 1, 0, -1, 0) encodes four directions: right (0,1), down (1,0), left (0,-1), and up (-1,0). The algorithm fills each position with incrementing values and changes direction whenever it hits a boundary or an already-filled cell.

Intuition

When we think about filling a matrix in spiral order, we can imagine walking along the edges of the matrix, always keeping the unfilled area to our right. It's like walking along the walls of a rectangular room, gradually spiraling inward.

The key insight is that we're essentially following a repeating pattern of four directions: right → down → left → up. We continue in one direction until we can't go further (either hitting a boundary or an already-filled cell), then we turn 90 degrees clockwise.

To implement this, we can use a clever trick with direction vectors. Instead of using separate if-else statements for each direction, we can encode all four directions in a single array. The pattern (0, 1, 0, -1, 0) gives us:

• Taking indices k and k+1: (0,1) means right, (1,0) means down, (0,-1) means left, (-1,0) means up
• When we need to turn, we just increment k by 1 (modulo 4 to wrap around)

The beauty of this approach is that we don't need to track complex boundary conditions for each layer of the spiral. We simply:

1. Fill the current position with the next number
2. Try to move in the current direction
3. If we can't (out of bounds or cell already filled), turn clockwise
4. Move to the next position

This natural "bump and turn" behavior automatically creates the spiral pattern, as the already-filled cells act like walls that guide our path inward. The algorithm naturally terminates when we've filled all n² positions.

Solution Approach

We implement the spiral matrix generation through simulation, following these steps:

1. Initialize the matrix and variables:

• Create an n x n matrix ans filled with zeros: ans = [[0] * n for _ in range(n)]
• Set position variables i = j = 0 to start at the top-left corner (0, 0)
• Define direction array dirs = (0, 1, 0, -1, 0) to encode four directions
• Initialize direction index k = 0 to start moving right

2. Direction encoding: The dirs array cleverly encodes all four directions:

• dirs[k] and dirs[k+1] give the row and column increments for direction k
• When k=0: (dirs[0], dirs[1]) = (0, 1) → move right
• When k=1: (dirs[1], dirs[2]) = (1, 0) → move down
• When k=2: (dirs[2], dirs[3]) = (0, -1) → move left
• When k=3: (dirs[3], dirs[4]) = (-1, 0) → move up

3. Fill the matrix iteratively: For each value v from 1 to n²:

• Fill current position: ans[i][j] = v
• Calculate next position: x, y = i + dirs[k], j + dirs[k + 1]
• Check if we need to turn:
  • If x < 0 or x >= n or y < 0 or y >= n (out of bounds)
  • Or if ans[x][y] is non-zero (already filled)
  • Then rotate clockwise: k = (k + 1) % 4
• Move to the next position: i, j = i + dirs[k], j + dirs[k + 1]

4. Key implementation details:

• The condition ans[x][y] works because Python treats non-zero values as True
• Using (k + 1) % 4 ensures the direction index wraps around from 3 back to 0
• The algorithm naturally terminates after filling all n² positions
• No need to explicitly track spiral layers or complex boundary conditions

The time complexity is O(n²) as we visit each cell exactly once, and the space complexity is O(n²) for storing the result matrix.

Example Walkthrough

Let's walk through creating a 3×3 spiral matrix step by step.

Initial Setup:

• Matrix: [[0, 0, 0], [0, 0, 0], [0, 0, 0]]
• Position: (i, j) = (0, 0)
• Direction array: dirs = (0, 1, 0, -1, 0)
• Direction index: k = 0 (moving right)

Step 1: Fill value 1

• Fill ans[0][0] = 1: [[1, 0, 0], [0, 0, 0], [0, 0, 0]]
• Next position: (0+0, 0+1) = (0, 1) - valid and empty
• Move to (0, 1)

Step 2: Fill value 2

• Fill ans[0][1] = 2: [[1, 2, 0], [0, 0, 0], [0, 0, 0]]
• Next position: (0+0, 1+1) = (0, 2) - valid and empty
• Move to (0, 2)

Step 3: Fill value 3

• Fill ans[0][2] = 3: [[1, 2, 3], [0, 0, 0], [0, 0, 0]]
• Next position: (0+0, 2+1) = (0, 3) - out of bounds!
• Turn clockwise: k = 1 (now moving down)
• New next position: (0+1, 2+0) = (1, 2)
• Move to (1, 2)

Step 4: Fill value 4

• Fill ans[1][2] = 4: [[1, 2, 3], [0, 0, 4], [0, 0, 0]]
• Next position: (1+1, 2+0) = (2, 2) - valid and empty
• Move to (2, 2)

Step 5: Fill value 5

• Fill ans[2][2] = 5: [[1, 2, 3], [0, 0, 4], [0, 0, 5]]
• Next position: (2+1, 2+0) = (3, 2) - out of bounds!
• Turn clockwise: k = 2 (now moving left)
• New next position: (2+0, 2-1) = (2, 1)
• Move to (2, 1)

Step 6: Fill value 6

• Fill ans[2][1] = 6: [[1, 2, 3], [0, 0, 4], [0, 6, 5]]
• Next position: (2+0, 1-1) = (2, 0) - valid and empty
• Move to (2, 0)

Step 7: Fill value 7

• Fill ans[2][0] = 7: [[1, 2, 3], [0, 0, 4], [7, 6, 5]]
• Next position: (2+0, 0-1) = (2, -1) - out of bounds!
• Turn clockwise: k = 3 (now moving up)
• New next position: (2-1, 0+0) = (1, 0)
• Move to (1, 0)

Step 8: Fill value 8

• Fill ans[1][0] = 8: [[1, 2, 3], [8, 0, 4], [7, 6, 5]]
• Next position: (1-1, 0+0) = (0, 0) - already filled!
• Turn clockwise: k = 0 (now moving right again)
• New next position: (1+0, 0+1) = (1, 1)
• Move to (1, 1)

Step 9: Fill value 9

• Fill ans[1][1] = 9: [[1, 2, 3], [8, 9, 4], [7, 6, 5]]
• All positions filled!

Final Result:

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

The path forms a clockwise spiral: starting from the top-left, moving right along the top edge, down the right edge, left along the bottom edge, up the left edge, and finally filling the center.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n²)

The algorithm fills an n × n matrix with values from 1 to n². The main loop iterates exactly n² times (from 1 to n * n + 1), and in each iteration, it performs constant-time operations:

• Setting a value in the matrix: O(1)
• Calculating next position: O(1)
• Checking boundaries and visited cells: O(1)
• Updating direction if needed: O(1)

Therefore, the overall time complexity is O(n²).

Space Complexity: O(1) (excluding the output array)

The algorithm uses only a fixed amount of extra space:

• Variables i, j, k for tracking position and direction: O(1)
• Variables x, y for checking next position: O(1)
• The dirs tuple with 5 constant elements: O(1)

The answer matrix ans of size n × n requires O(n²) space, but this is not counted in the space complexity analysis as it's part of the required output.

Therefore, the auxiliary space complexity is O(1).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Incorrect Direction Change Logic

Issue: A common mistake is checking the boundary conditions and changing direction AFTER moving to the new position, rather than checking BEFORE moving.

Incorrect approach:

# WRONG: Move first, then check
row += directions[direction_index]
col += directions[direction_index + 1]
if (row < 0 or row >= n or col < 0 or col >= n or matrix[row][col] != 0):
    # Too late! We've already moved to an invalid position
    direction_index = (direction_index + 1) % 4

Solution: Always validate the next position before moving. Calculate where you would go, check if it's valid, change direction if needed, then move.

Pitfall 2: Off-by-One Error in Direction Array Indexing

Issue: When using the compact direction array [0, 1, 0, -1, 0], forgetting that each direction uses two consecutive elements can lead to index out of bounds errors.

Incorrect approach:

directions = [0, 1, 0, -1, 0]
# WRONG: Trying to access directions[4] and directions[5] when direction_index = 4
next_row = row + directions[direction_index]
next_col = col + directions[direction_index + 1]  # IndexError when direction_index = 4

Solution: Always use modulo operation when incrementing the direction index to ensure it wraps around properly: direction_index = (direction_index + 1) % 4

Pitfall 3: Forgetting to Check Already-Filled Cells

Issue: Only checking boundary conditions without verifying if a cell is already filled will cause the spiral to overwrite previously placed values.

Incorrect approach:

# WRONG: Only checking boundaries, not if cell is already filled
if (next_row < 0 or next_row >= n or next_col < 0 or next_col >= n):
    direction_index = (direction_index + 1) % 4

Solution: Include a check for non-zero values (already filled cells) in your turn condition: matrix[next_row][next_col] != 0

Pitfall 4: Using Wrong Initial Values

Issue: Starting with the wrong value (0 instead of 1) or incorrect position leads to an incorrectly filled matrix.

Incorrect approach:

# WRONG: Starting from 0 instead of 1
for value in range(0, n * n):  # Results in matrix filled with 0 to n²-1
    matrix[row][col] = value

Solution: Ensure the loop starts from 1 and goes up to n²: range(1, n * n + 1)

Pitfall 5: Confusion with Direction Representation

Issue: Mixing up row and column increments when using different direction representations can cause the spiral to move incorrectly.

Alternative correct representations to avoid confusion:

# Method 1: Explicit direction vectors (clearer but more verbose)
directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]  # right, down, left, up
dr, dc = directions[direction_index]

# Method 2: Separate arrays for row and column changes
row_dirs = [0, 1, 0, -1]
col_dirs = [1, 0, -1, 0]

Solution: Pick one consistent representation and stick with it throughout your code. Add comments to clarify what each direction represents.