2326

2326. Spiral Matrix IV (Medium)

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:

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

Related Topics:
Array, Linked List, Matrix, Simulation

Similar Questions:

• Spiral Matrix (Medium)
• Spiral Matrix II (Medium)
• Spiral Matrix III (Medium)

Hints:

• First, generate an m x n matrix filled with -1s.
• Navigate within the matrix at (i, j) with the help of a direction vector ⟨di, dj⟩. At (i, j), you need to decide if you can keep going in the current direction.
• If you cannot keep going, rotate the direction vector clockwise by 90 degrees.

Solution 1.

// OJ: https://leetcode.com/problems/spiral-matrix-iv
// Author: github.com/lzl124631x
// Time: O(MN)
// Space: O(1)
class Solution {
public:
    vector<vector<int>> spiralMatrix(int m, int n, ListNode* head) {
        vector<vector<int>> ans(m, vector<int>(n, -1));
        int x = 0, y = 0, dirs[4][2] = {{0,1},{1,0},{0,-1},{-1,0}}, dir = 0;
        while (head) {
            ans[x][y] = head->val;
            head = head->next;
            int a = x + dirs[dir][0], b = y + dirs[dir][1];
            if (a < 0 || a >= m || b < 0 || b >= n || ans[a][b] != -1) dir = (dir + 1) % 4;
            x += dirs[dir][0], y += dirs[dir][1];
        }
        return ans;
    }
};