LeetCode 2326 - Spiral Matrix IV

LeetCode Problem 2326

Difficulty: 🟡 Medium
Topics: Array, Linked List, Matrix, Simulation

Solution

Problem Understanding

The problem gives us a linked list and asks us to place its values into an m x n matrix in clockwise spiral order.

We begin filling from the top-left corner of the matrix, which is position (0, 0). The traversal direction follows the standard spiral pattern:

1. Move left to right across the top row
2. Move top to bottom along the right column
3. Move right to left across the bottom row
4. Move bottom to top along the left column
5. Repeat inward until the matrix is completely processed

Each value from the linked list is written into the next spiral position. If the linked list runs out of nodes before the matrix is completely filled, every remaining empty cell must contain -1.

The input consists of:

• m, the number of rows
• n, the number of columns
• head, the head node of a singly linked list

The output is a fully constructed m x n matrix.

The constraints are important:

• 1 <= m * n <= 10^5
• The linked list length is at most m * n

This tells us that the total number of cells is at most 100000, so an O(m * n) solution is completely acceptable. However, anything significantly worse, such as repeatedly scanning for the next valid position, could become inefficient.

Several edge cases are important:

• The linked list may contain fewer values than the number of matrix cells
• The matrix may have only one row
• The matrix may have only one column
• The linked list may exactly fill the matrix
• Spiral traversal must stop correctly when boundaries overlap in odd-sized matrices

A naive implementation can easily overwrite cells or move outside matrix boundaries if spiral direction changes are not handled carefully.

Approaches

Brute Force Approach

A brute force solution would simulate movement cell by cell while repeatedly checking whether the next position is valid.

One possible implementation is:

• Maintain a current direction
• Move one step at a time
• If the next position is outside the matrix or already filled, rotate direction
• Continue until the linked list is exhausted

This approach works correctly because it explicitly simulates the spiral traversal order. However, if implemented poorly, it may repeatedly search for valid cells or perform excessive boundary checks.

Although the overall complexity can still be acceptable, the logic becomes more error-prone and less structured.

Optimal Approach

The better solution uses the classic spiral boundary technique.

Instead of dynamically detecting visited cells, we maintain four boundaries:

• top
• bottom
• left
• right

At each stage:

1. Fill the top row
2. Increment top
3. Fill the right column
4. Decrement right
5. Fill the bottom row
6. Decrement bottom
7. Fill the left column
8. Increment left

This method guarantees that every cell is visited exactly once in spiral order.

The key insight is that spiral traversal naturally shrinks inward layer by layer. By updating boundaries after completing each side, we avoid revisiting cells and eliminate the need for extra visited tracking.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(m × n)	O(m × n)	Simulates movement with repeated validity checks
Optimal	O(m × n)	O(m × n)	Uses shrinking spiral boundaries efficiently

Algorithm Walkthrough

1. Create an m x n matrix initialized with -1.

Initializing with -1 automatically handles unused cells if the linked list ends early. 2. Initialize four spiral boundaries:

• top = 0
• bottom = m - 1
• left = 0
• right = n - 1

These boundaries define the current unfilled rectangular region. 3. Store the linked list pointer in current.

This pointer tracks the next value to place into the matrix. 4. Continue processing while:

• current is not None
• the boundaries are still valid

5. Traverse from left to right across the top row.

For every column between left and right:

• Place the current linked list value
• Advance the linked list pointer

Stop immediately if the linked list becomes empty. 6. Increment top.

The top row is now fully processed and should not be revisited. 7. Traverse from top to bottom along the right column.

Repeat the same placement logic. 8. Decrement right.

The right column has been completed. 9. If boundaries are still valid, traverse from right to left across the bottom row.

This condition prevents duplicate traversal in single-row cases. 10. Decrement bottom. 11. If boundaries are still valid, traverse from bottom to top along the left column.

This condition prevents duplicate traversal in single-column cases.

1. Increment left.
2. Repeat until:

• the linked list is exhausted, or
• all matrix cells have been processed

1. Return the completed matrix.

Why it works

The algorithm maintains the invariant that all cells outside the current boundaries have already been filled in correct spiral order. Each traversal completely processes one side of the remaining rectangle, after which the corresponding boundary shrinks inward. Since boundaries only move inward and each cell belongs to exactly one layer, every cell is visited at most once and in the correct clockwise spiral sequence.

Python Solution

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

from typing import List, Optional

class Solution:
    def spiralMatrix(
        self,
        m: int,
        n: int,
        head: Optional[ListNode]
    ) -> List[List[int]]:
        
        matrix = [[-1] * n for _ in range(m)]

        top = 0
        bottom = m - 1
        left = 0
        right = n - 1

        current = head

        while current and top <= bottom and left <= right:

            # Left to right
            for col in range(left, right + 1):
                if not current:
                    break

                matrix[top][col] = current.val
                current = current.next

            top += 1

            # Top to bottom
            for row in range(top, bottom + 1):
                if not current:
                    break

                matrix[row][right] = current.val
                current = current.next

            right -= 1

            # Right to left
            if top <= bottom:
                for col in range(right, left - 1, -1):
                    if not current:
                        break

                    matrix[bottom][col] = current.val
                    current = current.next

                bottom -= 1

            # Bottom to top
            if left <= right:
                for row in range(bottom, top - 1, -1):
                    if not current:
                        break

                    matrix[row][left] = current.val
                    current = current.next

                left += 1

        return matrix

The implementation starts by creating a matrix filled with -1. This is important because any unfilled cells should remain -1 automatically after traversal ends.

The four boundary variables define the currently active spiral layer. After finishing one side of the spiral, the corresponding boundary moves inward.

The linked list pointer current is advanced every time a value is written into the matrix. Before each insertion, the code checks whether the linked list still contains nodes. This prevents dereferencing None.

The conditional checks before the bottom-row and left-column traversals are essential. Without them, single-row or single-column layers could be processed twice.

The algorithm continues until either:

• all linked list values are consumed, or
• the spiral boundaries collapse completely

Go Solution

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func spiralMatrix(m int, n int, head *ListNode) [][]int {

    matrix := make([][]int, m)

    for i := 0; i < m; i++ {
        matrix[i] = make([]int, n)

        for j := 0; j < n; j++ {
            matrix[i][j] = -1
        }
    }

    top := 0
    bottom := m - 1
    left := 0
    right := n - 1

    current := head

    for current != nil && top <= bottom && left <= right {

        // Left to right
        for col := left; col <= right && current != nil; col++ {
            matrix[top][col] = current.Val
            current = current.Next
        }

        top++

        // Top to bottom
        for row := top; row <= bottom && current != nil; row++ {
            matrix[row][right] = current.Val
            current = current.Next
        }

        right--

        // Right to left
        if top <= bottom {
            for col := right; col >= left && current != nil; col-- {
                matrix[bottom][col] = current.Val
                current = current.Next
            }

            bottom--
        }

        // Bottom to top
        if left <= right {
            for row := bottom; row >= top && current != nil; row-- {
                matrix[row][left] = current.Val
                current = current.Next
            }

            left++
        }
    }

    return matrix
}

The Go implementation follows the same spiral boundary logic as the Python version.

One important difference is matrix initialization. In Go, integer slices default to 0, so we must explicitly set every cell to -1.

Another difference is linked list handling. Go uses nil instead of Python's None, and linked list field access uses Val and Next.

The traversal loops include current != nil directly in loop conditions, which avoids extra nested checks.

Worked Examples

Example 1

Input:

m = 3
n = 5
head = [3,0,2,6,8,1,7,9,4,2,5,5,0]

Initial matrix:

-1	-1	-1	-1	-1
-1	-1	-1	-1	-1
-1	-1	-1	-1	-1

Step 1, Fill Top Row

Fill positions (0,0) through (0,4):

3	0	2	6	8
-1	-1	-1	-1	-1
-1	-1	-1	-1	-1

Update:

top = 1

Step 2, Fill Right Column

Fill downward:

3	0	2	6	8
-1	-1	-1	-1	1
-1	-1	-1	-1	7

Update:

right = 3

Step 3, Fill Bottom Row

Move right to left:

3	0	2	6	8
-1	-1	-1	-1	1
5	2	4	9	7

Update:

bottom = 1

Step 4, Fill Left Column

Move upward:

3	0	2	6	8
5	-1	-1	-1	1
5	2	4	9	7

Update:

left = 1

Step 5, Fill Inner Layer

Continue spiral traversal:

3	0	2	6	8
5	0	-1	-1	1
5	2	4	9	7

The linked list ends before all cells are filled, so remaining cells stay -1.

Final result:

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

Example 2

Input:

m = 1
n = 4
head = [0,1,2]

Initial matrix:

-1	-1	-1	-1

Only one row exists, so traversal proceeds left to right:

0	1	2	-1

The linked list ends, leaving the final cell as -1.

Final result:

[[0,1,2,-1]]

Complexity Analysis

Measure	Complexity	Explanation
Time	O(m × n)	Each matrix cell is processed at most once
Space	O(m × n)	The output matrix itself requires this space

The algorithm performs a constant amount of work per visited cell. Since every matrix position is filled at most once, the total runtime is linear in the number of cells.

The extra auxiliary space beyond the output matrix is only O(1), because we store a few boundary variables and a linked list pointer. However, the returned matrix itself occupies O(m × n) space.

Test Cases

# Helper utilities

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def build_list(values):
    dummy = ListNode()
    current = dummy

    for value in values:
        current.next = ListNode(value)
        current = current.next

    return dummy.next

solution = Solution()

# Example 1
head = build_list([3,0,2,6,8,1,7,9,4,2,5,5,0])
assert solution.spiralMatrix(3, 5, head) == [
    [3,0,2,6,8],
    [5,0,-1,-1,1],
    [5,2,4,9,7]
]  # Standard spiral fill with leftover cells

# Example 2
head = build_list([0,1,2])
assert solution.spiralMatrix(1, 4, head) == [
    [0,1,2,-1]
]  # Single row matrix

# Exact fill
head = build_list([1,2,3,4])
assert solution.spiralMatrix(2, 2, head) == [
    [1,2],
    [4,3]
]  # Linked list exactly fills matrix

# Single column
head = build_list([1,2,3])
assert solution.spiralMatrix(3, 1, head) == [
    [1],
    [2],
    [3]
]  # Single column traversal

# One element matrix
head = build_list([7])
assert solution.spiralMatrix(1, 1, head) == [
    [7]
]  # Smallest possible matrix

# Linked list shorter than matrix
head = build_list([1,2,3])
assert solution.spiralMatrix(2, 3, head) == [
    [1,2,3],
    [-1,-1,-1]
]  # Remaining cells should stay -1

# Odd dimension matrix
head = build_list([1,2,3,4,5,6,7,8,9])
assert solution.spiralMatrix(3, 3, head) == [
    [1,2,3],
    [8,9,4],
    [7,6,5]
]  # Spiral reaches center cell correctly

Test	Why
3 x 5 with leftover cells	Validates standard spiral traversal
1 x 4 matrix	Tests single-row handling
2 x 2 exact fill	Ensures no extra -1 values appear
3 x 1 matrix	Tests single-column traversal
1 x 1 matrix	Validates smallest boundary case
Short linked list	Confirms remaining cells stay -1
3 x 3 odd matrix	Ensures center cell handling is correct

Edge Cases

Single Row Matrix

A matrix with only one row can easily cause duplicate traversal bugs. After completing the top-row traversal, the bottom-row traversal could accidentally revisit the same row.

The implementation prevents this by checking:

if top <= bottom:

before traversing the bottom row.

Single Column Matrix

Similarly, matrices with one column can cause the left-column traversal to revisit cells already filled during the right-column traversal.

The implementation avoids this with:

if left <= right:

before traversing upward along the left side.

Linked List Shorter Than Matrix Capacity

The linked list may end before all matrix cells are filled. A buggy solution might continue traversal and attempt to access current.val after the pointer becomes None.

This implementation checks whether current exists before every insertion. Since the matrix starts fully initialized with -1, any untouched cells automatically contain the required value.

Odd-Sized Spiral Layers

In odd-dimension matrices such as 3 x 3 or 5 x 5, the spiral eventually collapses to a single center cell.

Incorrect boundary updates can skip or overwrite this center position. The boundary conditions in the algorithm ensure that each layer shrinks correctly and the center cell is processed exactly once.