Problem Description

You need to create a matrix filled with values from a linked list in a spiral pattern.

Given:

• Two integers m and n representing the dimensions of a matrix (m rows × n columns)
• The head of a linked list containing integers

Your task is to:

1. Create an m × n matrix
2. Fill the matrix with values from the linked list in a spiral order (clockwise), starting from the top-left corner (0, 0)
3. The spiral pattern moves: right → down → left → up → right (and repeats)
4. If the linked list has fewer elements than m × n, fill the remaining empty spaces with -1
5. Return the generated matrix

For example, if you have a 3×3 matrix and a linked list with values [1,2,3,4,5,6], the spiral filling would look like:

• Start at top-left, move right: fill positions (0,0), (0,1), (0,2) with values 1, 2, 3
• Turn down at the right edge: fill position (1,2) with value 4
• Turn left at the bottom-right: fill position (2,2) with value 5
• Continue left: fill position (2,1) with value 6
• Remaining positions would be filled with -1

The key challenge is to navigate the spiral pattern correctly, changing direction when you hit the matrix boundaries or already-filled cells.

Intuition

The spiral pattern is essentially about moving in one direction until we can't move anymore, then turning clockwise to the next direction. This is a classic simulation problem where we need to track our current position and direction.

Think about how you would manually fill a spiral: you'd start at the top-left corner and keep going right until you hit the edge. Then you'd turn down, go until you hit the bottom edge, turn left, and so on. The key insight is that we're always moving in one of four directions: right, down, left, or up, and we cycle through these directions in order.

To implement this, we can use a direction array to encode these four movements. The pattern (0, 1, 0, -1, 0) cleverly encodes the four directions:

• Right: (dirs[0], dirs[1]) = (0, 1) - row stays same, column increases
• Down: (dirs[1], dirs[2]) = (1, 0) - row increases, column stays same
• Left: (dirs[2], dirs[3]) = (0, -1) - row stays same, column decreases
• Up: (dirs[3], dirs[4]) = (-1, 0) - row decreases, column stays same

The direction index k cycles through 0, 1, 2, 3 to pick consecutive pairs from this array.

For detecting when to turn, we have two conditions:

1. We're about to go out of bounds (hit the matrix edge)
2. We're about to hit a cell we've already filled (which won't be -1 anymore)

Both conditions mean we can't continue in the current direction, so we turn clockwise by incrementing k (modulo 4 to wrap around). We keep trying directions until we find a valid move. If the linked list still has elements but we can't move in any direction from the current position, that would be impossible given the problem constraints - there will always be a valid next position if we haven't filled all cells yet.

This simulation approach naturally handles the spiral pattern without explicitly tracking boundaries or layers, making the code cleaner and easier to understand.

Learn more about Linked List patterns.

Solution Approach

We implement the spiral traversal using simulation with direction vectors. Here's how the solution works step by step:

1. Initialize the Matrix

ans = [[-1] * n for _ in range(m)]

Create an m × n matrix filled with -1. This serves two purposes: it's our output matrix, and -1 marks unfilled cells that we can move into.

2. Set Up Position and Direction Tracking

i = j = k = 0
dirs = (0, 1, 0, -1, 0)

• i, j: Current position in the matrix (starting at top-left corner (0, 0))
• k: Current direction index (0 = right, 1 = down, 2 = left, 3 = up)
• dirs: Encodes the four direction vectors. Using dirs[k] and dirs[k+1] gives us the row and column offsets for direction k

3. Main Traversal Loop

while 1:
    ans[i][j] = head.val
    head = head.next
    if head is None:
        break

For each node in the linked list:

• Fill the current position (i, j) with the node's value
• Move to the next node
• If we've exhausted the linked list, exit

4. Find Next Valid Position

while 1:
    x, y = i + dirs[k], j + dirs[k + 1]
    if 0 <= x < m and 0 <= y < n and ans[x][y] == -1:
        i, j = x, y
        break
    k = (k + 1) % 4

This inner loop finds where to move next:

• Calculate the next position (x, y) based on current direction k
• Check if (x, y) is valid:
  • Within matrix bounds: 0 <= x < m and 0 <= y < n
  • Not yet filled: ans[x][y] == -1
• If valid, update our position and continue
• If invalid, turn clockwise: k = (k + 1) % 4 and try the next direction

The modulo operation ensures we cycle through directions: right (0) → down (1) → left (2) → up (3) → right (0) again.

Time Complexity: O(m × n) - We visit each cell at most once Space Complexity: O(m × n) - For the output matrix (required by the problem)

The beauty of this approach is that it naturally handles the spiral pattern without explicitly tracking boundaries or spiral layers. The direction changes happen automatically when we hit filled cells or matrix edges.

Example Walkthrough

Let's trace through a small example to see how the spiral filling works.

Given:

• Matrix dimensions: m = 3, n = 4 (3 rows × 4 columns)
• Linked list: 3 → 0 → 2 → 6 → 8 → 1 → 7 → 9 → 4 → 2 → 5 → 5

Step-by-step execution:

Initial Setup:

• Matrix filled with -1:

  [-1, -1, -1, -1]
  [-1, -1, -1, -1]
  [-1, -1, -1, -1]

• Position: i = 0, j = 0 (top-left corner)
• Direction: k = 0 (moving right)
• Direction vectors: dirs = (0, 1, 0, -1, 0)

Filling Process:

1. Moving Right (k=0): direction vector is (0, 1)

   • Fill (0,0) with 3, move to (0,1)
   • Fill (0,1) with 0, move to (0,2)
   • Fill (0,2) with 2, move to (0,3)
   • Fill (0,3) with 6
   • Try to move to (0,4) - out of bounds! Turn to k=1 (down)

   Matrix state:

   [3,  0,  2,  6]
   [-1, -1, -1, -1]
   [-1, -1, -1, -1]

2. Moving Down (k=1): direction vector is (1, 0)

   • Fill (1,3) with 8, move to (2,3)
   • Fill (2,3) with 1
   • Try to move to (3,3) - out of bounds! Turn to k=2 (left)

   Matrix state:

   [3,  0,  2,  6]
   [-1, -1, -1, 8]
   [-1, -1, -1, 1]

3. Moving Left (k=2): direction vector is (0, -1)

   • Fill (2,2) with 7, move to (2,1)
   • Fill (2,1) with 9, move to (2,0)
   • Fill (2,0) with 4
   • Try to move to (2,-1) - out of bounds! Turn to k=3 (up)

   Matrix state:

   [3,  0,  2,  6]
   [-1, -1, -1, 8]
   [4,  9,  7,  1]

4. Moving Up (k=3): direction vector is (-1, 0)

   • Fill (1,0) with 2
   • Try to move to (0,0) - already filled (not -1)! Turn to k=0 (right)

   Matrix state:

   [3,  0,  2,  6]
   [2,  -1, -1, 8]
   [4,  9,  7,  1]

5. Moving Right Again (k=0): direction vector is (0, 1)

   • Fill (1,1) with 5, move to (1,2)
   • Fill (1,2) with 5
   • Linked list exhausted - done!

Final Matrix:

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

The algorithm successfully filled the matrix in spiral order: starting from top-left, going right along the top row, down the right column, left along the bottom row, up the left column, and finally right again to fill the remaining center cells. The direction changes happened automatically when we hit boundaries or already-filled cells.

Solution Implementation

Time and Space Complexity

Time Complexity: O(m × n)

The algorithm iterates through each cell of the m × n matrix exactly once. The outer while loop continues until all values from the linked list are placed or we reach the end of the list (whichever comes first). Each cell is visited at most once to place a value. The inner while loop for direction changes has at most 4 iterations (constant time) for each placement, which doesn't affect the overall complexity. Therefore, the time complexity is O(m × n).

Space Complexity: O(m × n)

The algorithm creates a 2D matrix ans with dimensions m × n to store the result. This matrix requires O(m × n) space. The additional variables (i, j, k, dirs, x, y) use only constant space O(1). Since the dominant space usage comes from the result matrix, the overall space complexity is O(m × n).

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

Common Pitfalls

1. Infinite Loop When All Directions Are Blocked

The most critical pitfall in this spiral matrix implementation is the potential for an infinite loop in the inner direction-finding loop. This occurs when the current position is surrounded by filled cells or boundaries in all four directions, but there are still nodes remaining in the linked list.

When This Happens:

• In smaller matrices where the spiral completes before the linked list is exhausted
• Example: A 2×2 matrix with a linked list containing 5+ elements

The Problem:

# After filling all 4 cells in a 2x2 matrix:
while True:
    next_row = row + directions[direction_idx]
    next_col = col + directions[direction_idx + 1]
  
    if (0 <= next_row < m and 
        0 <= next_col < n and 
        matrix[next_row][next_col] == -1):
        row, col = next_row, next_col
        break
  
    direction_idx = (direction_idx + 1) % 4
    # This loops forever if no valid position exists!

Solution: Add a counter to track direction changes and break after checking all four directions:

while head:
    matrix[row][col] = head.val
    head = head.next
  
    if head is None:
        break
  
    # Track how many directions we've tried
    directions_tried = 0
    while directions_tried < 4:
        next_row = row + directions[direction_idx]
        next_col = col + directions[direction_idx + 1]
      
        if (0 <= next_row < m and 
            0 <= next_col < n and 
            matrix[next_row][next_col] == -1):
            row, col = next_row, next_col
            break
      
        direction_idx = (direction_idx + 1) % 4
        directions_tried += 1
  
    # If we've tried all directions and found no valid position, stop
    if directions_tried == 4:
        break

2. Incorrect Direction Vector Indexing

Another common mistake is incorrectly accessing the direction vectors, especially forgetting that the directions array encodes pairs of values.

The Problem:

# Incorrect: treating directions as separate arrays
directions_row = [0, 1, 0, -1]
directions_col = [1, 0, -1, 0]
next_row = row + directions_row[direction_idx]  # Extra array overhead
next_col = col + directions_col[direction_idx]

Why the Original is Better: The single array directions = (0, 1, 0, -1, 0) is more efficient and elegant, but requires careful indexing with directions[k] and directions[k+1].

3. Not Handling Edge Case of Empty Linked List

If the linked list is empty (head is None), the code would crash when trying to access head.val.

Solution: Add an initial check:

def spiralMatrix(self, m: int, n: int, head: Optional[ListNode]) -> List[List[int]]:
    matrix = [[-1] * n for _ in range(m)]
  
    if not head:
        return matrix
  
    # Rest of the implementation...