Problem of The Day: Spiral Matrix IV

Problem Statement

Intuition

The problem is about filling a matrix in a spiral order while traversing a singly linked list. The matrix should be filled left to right, then top to bottom, right to left, and finally bottom to top, repeating this process until the matrix is fully populated or the linked list is exhausted.

Given this, my intuition is to simulate the spiral traversal of the matrix while filling it with the values from the linked list.

Approach

1. Start by initializing a matrix of size m x n filled with -1.
2. Maintain a pointer to the head of the linked list and begin filling the matrix.
3. Define boundaries and keep track of rows and columns to determine the directions in which the matrix should be filled:
   • First, fill left to right.
   • Then, fill top to bottom.
   • Then, fill right to left.
   • Finally, fill bottom to top.
4. Continue this process in a spiral manner while updating the matrix with the current node value from the linked list.
5. If the linked list is shorter than the matrix’s size, stop filling when the list ends.
6. Return the resulting matrix.

Complexity

• Time complexity: The time complexity of this solution is \(O(m \times n)\), as we are traversing each cell of the matrix exactly once, and the matrix has m x n cells.

• Space complexity: The space complexity is \(O(m \times n)\) as we are storing the matrix explicitly, which takes m x n space.

Code

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def spiralMatrix(self, m: int, n: int, head: Optional[ListNode]) -> List[List[int]]:
        mat = [[-1] * n for _ in range(m)]
        curr = head
        i = 0
        total = m * n
        direction = 1
        row, col = 0, -1
        while i < total:
            for _ in range(n):
                col += direction
                mat[row][col] = curr.val
                curr = curr.next
                if not curr:
                    return mat

            m -= 1
            for _ in range(m):
                row += direction
                mat[row][col] = curr.val
                curr = curr.next
                if not curr:
                    return mat
            n -= 1
            direction *= -1

            i += 1
        return mat

Editorial

Approach: Simulation

class Solution:
    def spiralMatrix(self, m: int, n: int, head: "ListNode") -> List[List[int]]:
        # Store the east, south, west, north movements in a matrix.
        i = 0
        j = 0
        cur_d = 0
        movement = [[0, 1], [1, 0], [0, -1], [-1, 0]]
        res = [[-1 for _ in range(n)] for _ in range(m)]

        while head is not None:
            res[i][j] = head.val
            newi = i + movement[cur_d][0]
            newj = j + movement[cur_d][1]

            # If we bump into an edge or an already filled cell, change the
            # direction.
            if (
                min(newi, newj) < 0
                or newi >= m
                or newj >= n
                or res[newi][newj] != -1
            ):
                cur_d = (cur_d + 1) % 4
            i += movement[cur_d][0]
            j += movement[cur_d][1]

            head = head.next

        return res

• time: O(n * m)
• space: O(1)