Spiral Matrix IV

Leetcode Problem:

• Spiral Matrix IV

Summary

• Generate a spiral matrix from a linked list of integers

Approach

• Use a spiral traversal algorithm to fill the matrix in a clockwise direction

Complexity

• O(R*C + N)

Explain

• The solution uses a spiral traversal algorithm to fill the matrix in a clockwise direction
• The algorithm starts from the top-left corner of the matrix and moves in a spiral pattern until all elements have been visited
• The matrix is represented as a 2D vector, and the algorithm uses two arrays `dy` and `dx` to keep track of the direction of movement
• The `R` and `C` variables represent the number of rows and columns in the matrix, respectively
• The algorithm also uses a `while` loop to iterate through the linked list and fill the matrix with the corresponding values
• The remaining empty spaces in the matrix are filled with -1.

Solution Code:

/**
 * 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> ans;
    
    int R, C;
    vector> spiralMatrix(int m, int n, ListNode* head) {
        int dy[] = {0, 1, 0, -1};
        int dx[] = {1, 0, -1, 0};
        R = m;
        C = n;

        vector> ans(m, vector(n, -1));
        int r = 0;
        int c = 0;
        int dir = 0;
        while(head){
            ans[r][c] = head->val;
            int nr = r + dy[dir];
            int nc = c + dx[dir];
            if (nr < 0 || nr >= R || nc < 0 || nc >= C || ans[nr][nc] != -1){
                dir = (dir + 1) %4;
                nr = r + dy[dir];
                nc = c + dx[dir];
            }
            r = nr;
            c = nc;
            head = head->next;
        }
        return ans;
    }
};