Leetcode Daily Question 09/09/2024 - 2326. Spiral Matrix IV

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.

class ListNode:
  def __init__(self, val = 0, next = None):
    self.val = val
    self.next = next
    
from typing import Optional, List
class Solution:
  def spiralMatrix(self, head: Optional[ListNode], m: int, n: int) -> List[List[int]]:
    new_matrix = [[-1] * n for _ in range(m)]
    left_wall = 0
    right_wall = n - 1
    top_wall = 0 
    bottom_wall = m - 1
    
    while head:
      for i in range(left_wall, right_wall + 1):
        if not head:
          break
        new_matrix[top_wall][i] = head.val
        head = head.next
      top_wall += 1

      for i in range(top_wall, bottom_wall + 1):
        if not head:
          break
        new_matrix[i][right_wall] = head.val
        head = head.next
      right_wall -= 1

      for i in range(right_wall, left_wall - 1, -1):
        if not head:
          break
        new_matrix[bottom_wall][i] = head.val
        head = head.next
      bottom_wall -= 1

      for i in range(bottom_wall, top_wall - 1, -1):
        if not head:
          break
        new_matrix[i][left_wall] = head.val
        head = head.next
      left_wall += 1
    return new_matrix

Explanation:

We solve this by traversing the linked list to obtain the values for the matrix cells. We can create the spiral pattern by treating the matrix as a bounding box. Every time we hit a side (wall) of the matrix, we turn clockwise pi/2, and shrink the side we just traversed.

To make things easier, we can also initiate each cell of the matrix with "-1". This saves time as we do not need to traverse the entire matrix if the linked list has less nodes than matrix has cells.

Let's start by defining the matrix and its walls

new_matrix = [[-1] * n for _ in range(m)]
left_wall = 0
right_wall = n - 1
top_wall = 0
bottom_wall = m - 1

while head: # We only need to fill in all the values associated with the linked list. 
  for i in range(left_wall, right_wall + 1): # Move right.
    if not head: # Early termination if the linked list null.
      break
    new_matrix[top_wall][i] = head.val
    head = head.next
  top_wall += 1 # Shrink the bounding box

  for i in range(top_wall, bottom_wall + 1): # Move down.
    if not head:
      break
    new_matrix[i][right_wall] = head.val
    head = head.next
  right_wall -= 1 # Shrink the bounding box

  for i in range(right_wall, left_wall - 1, -1): # Move left.
    if not head:
      break
    new_matrix[bottom_wall][i] = head.val
    head = head.next
  bottom_wall -= 1 # Shrink the bounding box

  for i in range(bottom_wall, top_wall - 1, -1): # Move up.
    if not head:
      break
    new_matrix[i][left_wall] = head.val
    head = head.next
  left_wall += 1 # Shrink the bounding box

return new_matrix

The time complexity is O(m*n) as we potential traverse the entire new_matrix.

The space complexity is O(m*n) as we store the new_matrix as a list of lists.

The full solution can be found near the top of the page.