We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Spiral Matrix IV

Difficulty: Medium

Problem Description

You are given two integers m and n, which represent the dimensions of a matrix. You are also given the head of a linked list of integers. Generate an m x n matrix that contains the integers in the linked list presented in spiral order (clockwise), starting from the top-left of the matrix. If there are remaining empty spaces, fill them with -1. Return the generated matrix.

Key Insights

  • The matrix is filled in a spiral order, which requires careful tracking of boundaries (top, bottom, left, right) to avoid overwriting cells.
  • Use a linked list to populate the matrix, managing the transition from one row or column to the next as the spiral progresses.
  • Any remaining cells after the linked list has been exhausted should be filled with -1.

Space and Time Complexity

Time Complexity: O(m * n) - We need to fill every cell in the m x n matrix. Space Complexity: O(1) - We are using the output matrix in place and not requiring additional space proportional to the input size.

Solution

To solve this problem, we will:

  1. Initialize an m x n matrix filled with -1.
  2. Use four pointers to track the boundaries of the spiral (top, bottom, left, right).
  3. Iterate through the linked list, filling the matrix in a spiral manner while adjusting the boundaries as we fill each layer of the spiral.
  4. If we run out of elements in the linked list before filling the matrix, the remaining cells will already be set to -1.

Code Solutions

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

def spiralMatrix(m, n, head):
    # Initialize the matrix with -1
    matrix = [[-1] * n for _ in range(m)]
    
    # Pointers for the boundaries of the spiral
    top, bottom, left, right = 0, m - 1, 0, n - 1
    
    # Current node in the linked list
    current = head
    
    while top <= bottom and left <= right:
        # Fill from left to right
        for i in range(left, right + 1):
            if current:
                matrix[top][i] = current.val
                current = current.next
        top += 1
        
        # Fill from top to bottom
        for i in range(top, bottom + 1):
            if current:
                matrix[i][right] = current.val
                current = current.next
        right -= 1
        
        if top <= bottom:
            # Fill from right to left
            for i in range(right, left - 1, -1):
                if current:
                    matrix[bottom][i] = current.val
                    current = current.next
            bottom -= 1
            
        if left <= right:
            # Fill from bottom to top
            for i in range(bottom, top - 1, -1):
                if current:
                    matrix[i][left] = current.val
                    current = current.next
            left += 1
            
    return matrix
← Back to All Questions