[Solved] Spiral Matrix IV LeetCode Contest Problem

Spiral Matrix IV: 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.

Spiral Matrix IV LeetCode Contest

Example 1:

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:

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

Solution

vector<vector<int>> spiralMatrix(int m, int n, ListNode* head) {
    int i = 0, j = 0, cur_d = 0, d[5] = {0, 1, 0, -1, 0};
    vector<vector<int>> res(m, vector<int>(n, -1));
    for (; head != nullptr; head = head->next) {
        res[i][j] = head->val;
        int ni = i + d[cur_d], nj = j + d[cur_d + 1];
        if (min(ni, nj) < 0 || ni >= m || nj >= n || res[ni][nj] != -1)
            cur_d = (cur_d + 1) % 4;
        i += d[cur_d];
        j += d[cur_d + 1];
    }
    return res;
}

The idea to take from this is how to rotate the direction in a concise way.

Initially, we start by adding 1 to the column, and 0 to the row (going right)

If we hit a wall/edge, we must swap the direction. The trick is to swap with:

xr, xc = xc, -xr

Let xr be the term we add to our r row in every move.
Let xc be the term we add to our c column in every move.

class Solution:
    def spiralMatrix(self, m: int, n: int, head: Optional[ListNode]) -> List[List[int]]:
        r, c = 0, 0
        xr, xc = 0, 1
        
        matrix = [[-1 for _ in range(n)] for _ in range(m)]
        while head:
            matrix[r][c] = head.val
            
            # Conditions to swap the direction
            if r + xr < 0 or r + xr >= m or c + xc < 0 or c + xc >= n or matrix[r+xr][c+xc] != -1:
                xr, xc = xc, -xr
            
            r += xr
            c += xc
            head = head.next
        
        return matrix

/**
 * 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 [][]arr=new int[m][n];
        int i,j;
        int top=0,down=m-1,left=0,right=n-1;
        for(int fill[] : arr) Arrays.fill(fill,-1);
        while(head!=null)
        {
            for(i=left;i<=right;i++)
            {
                if(head==null)
                {
                    break;
                }
                arr[top][i]=head.val;
                head=head.next;
            }
            top++;
            for(i=top;i<=down;i++)
            {
                if(head==null)
                {
                    break;
                }
                arr[i][right]=head.val;
                head=head.next;
            }
            right--;
            for(i=right;i>=left;i--)
            {
                if(head==null)
                {
                    break;
                }
                arr[down][i]=head.val;
                head=head.next;
            }
            down--;
            for(i=down;i>=top;i--)
            {
                if(head==null)
                {
                    break;
                }
                arr[i][left]=head.val;
                head=head.next;
            }
            left++;
            
        }
        
        return arr;
    }
}

Happy Learning – If you require any further information, feel free to contact me.