LeetCode Solutions Blog

Spiral Matrix IV

Number: 2411

Difficulty: Medium

Paid? No

Companies: Meta, Google

Problem Description

Given the dimensions m and n for a matrix and the head of a linked list, fill an m x n matrix in spiral order (clockwise) with the values from the linked list, starting at the top-left. If the linked list is exhausted before the matrix is fully filled, populate the remaining entries with -1.

Key Insights

We need to traverse the matrix in a spiral order: right across the top row, then down the right column, left across the bottom row, and finally up the left column.
The matrix is initialized with -1, which is used to fill the cells that are not populated with linked list values.
We maintain boundaries (top, bottom, left, right) and update them after each spiral pass.
Continue the spiral until either the linked list is exhausted or all cells are filled.
Handling boundary conditions carefully avoids overstepping or double filling.

Space and Time Complexity

Time Complexity: O(m * n), since every cell is visited once.
Space Complexity: O(m * n) for the output matrix, with O(1) extra space for the pointers and boundary variables.

Solution

The solution uses a simulation approach. After initializing the matrix with -1, we set four boundary pointers (top, bottom, left, right) representing the current limits of unfilled cells. We then loop through the following steps:

Fill the top row from the left boundary to the right boundary.
Move the top boundary down.
Fill the right column from the updated top to the bottom.
Move the right boundary left.
If there is an available row, fill the bottom row from the updated right to the left.
Move the bottom boundary up.
If there is an available column, fill the left column from the updated bottom up.
Move the left boundary right. Continue this process until you have either filled the entire matrix or exhausted the linked list. Each step checks whether the current pointer in the list is still valid before assignment.

Code Solutions

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

def spiralMatrix(m, n, head):
    # Initialize an m x n matrix filled with -1.
    matrix = [[-1] * n for _ in range(m)]
    
    # Define boundaries for spiral traversal.
    top, bottom = 0, m - 1
    left, right = 0, n - 1
    
    current = head  # Pointer to traverse the linked list.
    
    # Fill the matrix in spiral order.
    while current and top <= bottom and left <= right:
        # Fill the top row from left to right.
        for j in range(left, right + 1):
            if not current:
                break
            matrix[top][j] = current.val
            current = current.next
        top += 1
        
        # Fill the right column from top to bottom.
        for i in range(top, bottom + 1):
            if not current:
                break
            matrix[i][right] = current.val
            current = current.next
        right -= 1
        
        # Fill the bottom row from right to left.
        if top <= bottom:
            for j in range(right, left - 1, -1):
                if not current:
                    break
                matrix[bottom][j] = current.val
                current = current.next
            bottom -= 1
        
        # Fill the left column from bottom to top.
        if left <= right:
            for i in range(bottom, top - 1, -1):
                if not current:
                    break
                matrix[i][left] = current.val
                current = current.next
            left += 1
            
    return matrix

# Helper function to build a linked list from an Python list.
def buildLinkedList(values):
    dummy = ListNode(0)
    current = dummy
    for val in values:
        current.next = ListNode(val)
        current = current.next
    return dummy.next

# Example usage:
# m = 3, n = 5, head = [3,0,2,6,8,1,7,9,4,2,5,5,0]
headNode = buildLinkedList([3,0,2,6,8,1,7,9,4,2,5,5,0])
result = spiralMatrix(3, 5, headNode)
print(result)