LEET CODE POTD: 2326. Spiral Matrix IV

The “Spiral Matrix IV” problem (LeetCode #2326) requires constructing a spiral matrix from a linked list, filling the matrix with the values from the list in spiral order.

Problem Description:

You’re given two integers m and n representing the dimensions of a matrix, and the head of a linked list. The task is to create an m x n matrix filled with the values from the linked list in spiral order. If the linked list contains fewer elements than the matrix, fill the remaining cells with -1.

Approach:

1. Initialize a Matrix: Start by initializing a matrix of size m x n with default values of -1.
2. Define Spiral Movement: The movement will follow the typical spiral order (right → down → left → up). Use direction vectors to handle the movement.
3. Fill the Matrix: Starting from the top-left corner, place the values from the linked list into the matrix in spiral order. If the linked list ends, fill the remaining cells with -1.

Detailed Steps:

1. Create an Empty Matrix: Initialize an empty matrix with m rows and n columns, all initially set to -1.
2. Movement in Spiral Order:

• Define the directions for moving right, down, left, and up. Use a direction vector that cycles through these four directions.
• Keep track of the current position in the matrix and ensure that you don’t overwrite already filled cells or move outside the matrix.

1. Traverse the Linked List:

• Start at the first element of the matrix and traverse the linked list.
• For each node, fill the current matrix cell with the node’s value and then move in the current direction.
• If the move goes out of bounds or encounters an already filled cell, change direction and continue.

1. End of Linked List:

• Once the linked list is exhausted, fill the remaining cells with -1.

Solution:

JavaScript Code:

// Definition for singly-linked list.
function ListNode(val, next) {
    this.val = (val===undefined ? 0 : val);
    this.next = (next===undefined ? null : next);
}

var spiralMatrix = function(m, n, head) {
    // Step 1: Initialize the matrix with -1
    const matrix = Array.from({ length: m }, () => Array(n).fill(-1));

    // Step 2: Define the directions for spiral traversal: right, down, left, up
    const directions = [[0, 1], [1, 0], [0, -1], [-1, 0]];
    let dirIdx = 0; // Direction index to cycle through directions
    let row = 0, col = 0; // Starting position

    let curr = head; // Pointer to traverse the linked list

    // Step 3: Traverse the matrix and fill it in spiral order
    for (let i = 0; i < m * n && curr; i++) {
        matrix[row][col] = curr.val; // Fill the current cell with the linked list value
        curr = curr.next; // Move to the next node in the linked list

        // Calculate the next position
        let newRow = row + directions[dirIdx][0];
        let newCol = col + directions[dirIdx][1];

        // Check if the new position is out of bounds or already filled
        if (newRow < 0 || newRow >= m || newCol < 0 || newCol >= n || matrix[newRow][newCol] !== -1) {
            // Change direction if the move is not valid
            dirIdx = (dirIdx + 1) % 4;
            newRow = row + directions[dirIdx][0];
            newCol = col + directions[dirIdx][1];
        }

        // Move to the next position
        row = newRow;
        col = newCol;
    }

    return matrix;
};

// Usage example:

// Create a linked list: 3 -> 0 -> 2 -> 6 -> 8 -> 1 -> 7 -> 9 -> 4
let head = new ListNode(3, new ListNode(0, new ListNode(2, new ListNode(6, new ListNode(8, new ListNode(1, new ListNode(7, new ListNode(9, new ListNode(4)))))))));

let result = spiralMatrix(3, 5, head);
console.log(result);

Explanation:

1. Matrix Initialization:

• We initialize the matrix with dimensions m x n, where all values are initially -1.

1. Spiral Movement:

• The direction vectors are right (0,1), down (1,0), left (0,-1), and up (-1,0). We cycle through these directions as we move in spiral order.

1. Linked List Traversal:

• Starting from the top-left corner, we place the values from the linked list into the matrix. Each time we place a value, we check if the next move is valid. If it isn’t (i.e., we’re out of bounds or the cell is already filled), we change the direction.

1. Edge Cases:

• If the linked list has fewer elements than the matrix can hold, we fill the remaining cells with -1.

Time Complexity:

• O(m * n): We visit each cell in the matrix exactly once.

Space Complexity:

• O(m * n): The matrix size is proportional to m * n, and we also use a constant amount of additional space for pointers and variables.

This solution constructs the matrix efficiently by filling it in spiral order and handling linked list traversal at the same time.