Welcome to Subscribe On Youtube

2326. Spiral Matrix IV

Description

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

Solutions

• Java
• C++
• Python
• Go
• TypeScript

• /**
   * 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;
      }
  }
  

• /**
   * 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;
      }
  };
  

• # 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
  
  

• /**
   * Definition for singly-linked list.
   * type ListNode struct {
   *     Val int
   *     Next *ListNode
   * }
   */
  func spiralMatrix(m int, n int, head *ListNode) [][]int {
  	ans := make([][]int, m)
  	for i := range ans {
  		ans[i] = make([]int, n)
  		for j := range ans[i] {
  			ans[i][j] = -1
  		}
  	}
  	i, j, p := 0, 0, 0
  	dirs := [][]int{ {0, 1}, {1, 0}, {0, -1}, {-1, 0} }
  	for {
  		ans[i][j] = head.Val
  		head = head.Next
  		if head == nil {
  			break
  		}
  		for {
  			x, y := i+dirs[p][0], j+dirs[p][1]
  			if x < 0 || y < 0 || x >= m || y >= n || ans[x][y] >= 0 {
  				p = (p + 1) % 4
  			} else {
  				i, j = x, y
  				break
  			}
  		}
  	}
  	return ans
  }
  

• /**
   * Definition for singly-linked list.
   * class ListNode {
   *     val: number
   *     next: ListNode | null
   *     constructor(val?: number, next?: ListNode | null) {
   *         this.val = (val===undefined ? 0 : val)
   *         this.next = (next===undefined ? null : next)
   *     }
   * }
   */
  
  function spiralMatrix(m: number, n: number, head: ListNode | null): number[][] {
      const dirs = [
          [0, 1],
          [1, 0],
          [0, -1],
          [-1, 0],
      ];
      let ans = Array.from({ length: m }, v => new Array(n).fill(-1));
      let i = 0,
          j = 0,
          k = 0;
      while (head) {
          ans[i][j] = head.val;
          head = head.next;
          let x = i + dirs[k][0];
          let y = j + dirs[k][1];
          if (x < 0 || x > m - 1 || y < 0 || y > n - 1 || ans[x][y] != -1) {
              k = (k + 1) % 4;
          }
          i = i + dirs[k][0];
          j = j + dirs[k][1];
      }
      return ans;
  }
  
  

All Problems

All Solutions