# Spiral Matrix IV
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/spiral-matrix-iv)
Canonical: https://scaleengineer.com/dsa/problems/spiral-matrix-iv
**Data structures:** Array, Linked List, Matrix
---
## Problem
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_.

**Example 1:**

![](https://assets.glich.co/dsa/spiral-matrix-iv/image0.jpg) 

**Input:** m = 3, n = 5, head = [3,0,2,6,8,1,7,9,4,2,5,5,0]
**Output:** [[3,0,2,6,8],[5,0,-1,-1,1],[5,2,4,9,7]]
**Explanation:** The diagram above shows how the values are printed in the matrix.
Note that the remaining spaces in the matrix are filled with -1.

**Example 2:**

![](https://assets.glich.co/dsa/spiral-matrix-iv/image1.jpg) 

**Input:** m = 1, n = 4, head = [0,1,2]
**Output:** [[0,1,2,-1]]
**Explanation:** The diagram above shows how the values are printed from left to right in the matrix.
The last space in the matrix is set to -1.

**Constraints:**

* `1 <= m, n <= 105`
* `1 <= m * n <= 105`
* The number of nodes in the list is in the range `[1, m * n]`.
* `0 <= Node.val <= 1000`

# Approaches
## Simulation with Direction Array and Visited Matrix
This approach simulates the spiral traversal by keeping track of the current position `(row, col)` and the current direction of movement. It uses a separate `visited` matrix to avoid revisiting cells and to know when to change direction.
**Time:** O(m * n) · **Space:** O(m * n)
**Pros:** The logic is a direct simulation of a point moving and turning, which can be intuitive to reason about.
**Cons:** Requires O(m * n) extra space for the `visited` matrix, making it less space-efficient than the layer-by-layer approach.
### Explanation
In this method, we simulate the path of a point moving through the matrix. We begin by creating the `m x n` result matrix and pre-filling it with `-1`. This handles the requirement for default values in unused cells. We also need a second `m x n` boolean matrix, `visited`, to keep track of which cells have been filled.

The traversal starts at the top-left corner `(0, 0)`. We maintain the current direction of travel (e.g., right, down, left, up). We iterate as long as there are nodes left in the linked list. In each step, we fill the current cell, mark it as visited, and advance the linked list pointer. Then, we check if the next cell in the current direction is valid (i.e., within the matrix boundaries and not yet visited). If it's not valid, we know we've hit a wall or a previously filled path, so we turn clockwise to the next direction. Finally, we update our current coordinates to move to the next cell. This process naturally carves out a spiral path.

```java
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public int[][] spiralMatrix(int m, int n, ListNode head) {
        int[][] matrix = new int[m][n];
        for (int i = 0; i < m; i++) {
            java.util.Arrays.fill(matrix[i], -1);
        }

        boolean[][] visited = new boolean[m][n];
        int[] dr = {0, 1, 0, -1}; // Direction vectors for row
        int[] dc = {1, 0, -1, 0}; // Direction vectors for col
        int row = 0, col = 0, dir = 0;
        ListNode curr = head;

        // We can iterate m * n times, as that's the max number of cells to fill.
        for (int i = 0; i < m * n; i++) {
            if (curr == null) {
                break;
            }
            matrix[row][col] = curr.val;
            visited[row][col] = true;
            curr = curr.next;

            int nextRow = row + dr[dir];
            int nextCol = col + dc[dir];

            if (nextRow < 0 || nextRow >= m || nextCol < 0 || nextCol >= n || visited[nextRow][nextCol]) {
                dir = (dir + 1) % 4; // Change direction
            }
            
            row += dr[dir];
            col += dc[dir];
        }

        return matrix;
    }
}
```
### Algorithm
- Create an `m x n` result matrix `matrix` and initialize all its elements to `-1`.
- Create an `m x n` boolean matrix `visited` and initialize all its elements to `false`.
- Initialize the starting position `(row, col)` to `(0, 0)` and the initial direction `dir` to `0` (representing 'right').
- Define direction vectors for row and column changes: `dr = {0, 1, 0, -1}` and `dc = {1, 0, -1, 0}`.
- Use a pointer `curr` to traverse the linked list, starting from the `head`.
- Loop as long as `curr` is not `null`:
  1. Place the value `curr.val` at `matrix[row][col]`.
  2. Mark the cell as visited: `visited[row][col] = true`.
  3. Advance the list pointer: `curr = curr.next`.
  4. If the list is exhausted, break the loop.
  5. Calculate the next potential position `(nextRow, nextCol)` using the current direction.
  6. If `(nextRow, nextCol)` is out of bounds or has already been visited, change the direction by turning clockwise: `dir = (dir + 1) % 4`.
  7. Update the current position `(row, col)` using the new direction.
- Return the `matrix`.

## Simulation with Layer-by-Layer Traversal
This is the most common and efficient approach for spiral matrix problems. It works by traversing the matrix in layers, from the outermost layer to the innermost. Four pointers (`top`, `bottom`, `left`, `right`) are used to define the boundaries of the current layer being traversed, and these boundaries shrink after each side is completed.
**Time:** O(m * n), as each cell of the matrix is visited and filled exactly once. · **Space:** O(1) auxiliary space. The O(m * n) space for the output matrix is required by the problem and not considered auxiliary.
**Pros:** Optimal space complexity, as it only uses a few variables for pointers and does not require an auxiliary `visited` matrix.; Highly efficient time complexity, visiting each cell exactly once.
**Cons:** The logic involving four separate loops and updating boundaries can be slightly more complex to implement without off-by-one errors.
### Explanation
This optimal approach avoids the need for an extra `visited` matrix by intelligently shrinking the boundaries of the matrix after each full pass of a row or column. We start by initializing the `m x n` result matrix with `-1`.

We define four pointers: `top`, `bottom`, `left`, and `right`, which represent the boundaries of the current rectangular layer we are filling. Initially, they correspond to the full matrix dimensions.

The process is a loop that continues as long as the boundaries have not crossed (i.e., `top <= bottom` and `left <= right`) and we still have nodes in our linked list.

Inside the loop, we perform four distinct steps to fill the four sides of the current layer in a clockwise direction:
1.  Fill the top row from left to right.
2.  Fill the rightmost column from top to bottom.
3.  Fill the bottom row from right to left.
4.  Fill the leftmost column from bottom to top.

After each step, we update the corresponding boundary pointer (e.g., after filling the top row, we increment `top`) to shrink the area for the next iteration. We must also check if the linked list has been exhausted before filling each cell. The conditions `if (top <= bottom)` and `if (left <= right)` are crucial before the third and fourth steps to handle matrices that are not square (e.g., a single row or column).

```java
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public int[][] spiralMatrix(int m, int n, ListNode head) {
        int[][] matrix = new int[m][n];
        for (int i = 0; i < m; i++) {
            java.util.Arrays.fill(matrix[i], -1);
        }

        int top = 0, bottom = m - 1;
        int left = 0, right = n - 1;
        ListNode curr = head;

        while (curr != null && top <= bottom && left <= right) {
            // Traverse Right
            for (int j = left; j <= right && curr != null; j++) {
                matrix[top][j] = curr.val;
                curr = curr.next;
            }
            top++;

            // Traverse Down
            for (int i = top; i <= bottom && curr != null; i++) {
                matrix[i][right] = curr.val;
                curr = curr.next;
            }
            right--;

            // Traverse Left (check if row still exists)
            if (top <= bottom) {
                for (int j = right; j >= left && curr != null; j--) {
                    matrix[bottom][j] = curr.val;
                    curr = curr.next;
                }
                bottom--;
            }

            // Traverse Up (check if column still exists)
            if (left <= right) {
                for (int i = bottom; i >= top && curr != null; i--) {
                    matrix[i][left] = curr.val;
                    curr = curr.next;
                }
                left++;
            }
        }
        return matrix;
    }
}
```
### Algorithm
- Create an `m x n` result matrix `matrix` and initialize all its elements to `-1`.
- Initialize four boundary pointers: `top = 0`, `bottom = m - 1`, `left = 0`, `right = n - 1`.
- Use a pointer `curr` to traverse the linked list, starting from the `head`.
- Loop as long as `top <= bottom` and `left <= right`.
  1. **Traverse Right:** Iterate from `j = left` to `right`. In each step, if `curr` is not null, set `matrix[top][j] = curr.val` and advance `curr`. After the row is filled, increment `top`.
  2. **Traverse Down:** Iterate from `i = top` to `bottom`. If `curr` is not null, set `matrix[i][right] = curr.val` and advance `curr`. After the column is filled, decrement `right`.
  3. **Traverse Left:** Check if `top <= bottom`. If so, iterate from `j = right` to `left`. If `curr` is not null, set `matrix[bottom][j] = curr.val` and advance `curr`. After the row is filled, decrement `bottom`.
  4. **Traverse Up:** Check if `left <= right`. If so, iterate from `i = bottom` to `top`. If `curr` is not null, set `matrix[i][left] = curr.val` and advance `curr`. After the column is filled, increment `left`.
- If `curr` becomes `null` at any point, the loops will continue but won't fill any more cells, effectively terminating the process.
- Return the `matrix`.

# Solutions
### Java

```java
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */ class Solution { public int [][] spiralMatrix ( int m , int n , ListNode head ) { int [][] ans = new int [ m ][ n ]; for ( int [] row : ans ) { Arrays . fill ( row , - 1 ); } int i = 0 , j = 0 , p = 0 ; int [][] dirs = { { 0 , 1 }, { 1 , 0 }, { 0 , - 1 }, {- 1 , 0 } }; while ( true ) { ans [ i ][ j ] = head . val ; head = head . next ; if ( head == null ) { break ; } while ( true ) { int x = i + dirs [ p ][ 0 ], y = j + dirs [ p ][ 1 ]; if ( x < 0 || y < 0 || x >= m || y >= n || ans [ x ][ y ] >= 0 ) { p = ( p + 1 ) % 4 ; } else { i = x ; j = y ; break ; } } } return ans ; } }
```

### CPP

```cpp
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */ class Solution { public: vector < vector < int >> spiralMatrix ( int m , int n , ListNode * head ) { vector < vector < int >> ans ( m , vector < int > ( n , - 1 )); int i = 0 , j = 0 , p = 0 ; vector < vector < int >> dirs = { { 0 , 1 }, { 1 , 0 }, { 0 , - 1 }, { - 1 , 0 } }; while ( 1 ) { ans [ i ][ j ] = head -> val ; head = head -> next ; if ( ! head ) break ; while ( 1 ) { int x = i + dirs [ p ][ 0 ], y = j + dirs [ p ][ 1 ]; if ( x < 0 || y < 0 || x >= m || y >= n || ans [ x ][ y ] >= 0 ) p = ( p + 1 ) % 4 ; else { i = x , j = y ; break ; } } } return ans ; } };
```

### Python

```python
# 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 ]]: ans = [[ - 1 ] * n for _ in range ( m )] i = j = p = 0 dirs = [[ 0 , 1 ], [ 1 , 0 ], [ 0 , - 1 ], [ - 1 , 0 ]] while 1 : ans [ i ][ j ] = head . val head = head . next if not head : break while 1 : x , y = i + dirs [ p ][ 0 ], j + dirs [ p ][ 1 ] if x < 0 or y < 0 or x >= m or y >= n or ~ ans [ x ][ y ]: p = ( p + 1 ) % 4 else : i , j = x , y break return ans
```