NeetCode #905LC-2326MediumMath & Geometry
← Back to All Problems#905 · #2326 · Spiral Matrix IV(螺旋矩阵 IV)
📌 Problem Statement & Constraints
Given two integers
m and n and the head of a singly linked list, fill an m x n matrix with the list's values in spiral order, starting at the top-left and moving clockwise inward. Cells not reached keep the value -1. Constraints: 1 <= m, n <= 10^5, 1 <= m * n <= 10^5, 0 <= Node.val <= 10^5.💡 Core Algorithmic Approaches
- Use the standard four-boundary spiral traversal, exactly as in Spiral Matrix II.
- Instead of a counter, advance a pointer through the linked list, writing the current node's value into the current cell.
- The list may be shorter than the matrix, so the pointer must be checked inside each inner loop; once it is
None, return the matrix immediately. - The remaining unfilled cells retain their initial sentinel value
-1.
💻 Benchmark Python3 Implementation
class Solution:
def spiralMatrix(self, m: int, n: int, head: Optional[ListNode]) -> List[List[int]]:
res = [[-1] * n for _ in range(m)]
top, bottom, left, right = 0, m - 1, 0, n - 1
cur = head
while cur and top <= bottom and left <= right:
for j in range(left, right + 1):
if cur is None:
return res
res[top][j] = cur.val
cur = cur.next
top += 1
for i in range(top, bottom + 1):
if cur is None:
return res
res[i][right] = cur.val
cur = cur.next
right -= 1
if top <= bottom:
for j in range(right, left - 1, -1):
if cur is None:
return res
res[bottom][j] = cur.val
cur = cur.next
bottom -= 1
if left <= right:
for i in range(bottom, top - 1, -1):
if cur is None:
return res
res[i][left] = cur.val
cur = cur.next
left += 1
return res⚡ Complexity Deep Dive
⏱️ Time Complexity
O(m * n): each cell is visited at most once.
💾 Space Complexity
O(m * n): the output matrix.
⚠️ Interview Pitfalls & Follow-ups
- Checking
cur is Noneonly at the top of the outer loop: the list can end mid-side, so the guard belongs inside every inner loop. - Initialising cells to
0: the required sentinel for unfilled cells is-1. - Assuming the list length equals
m * n: the list may be shorter or the same length, and the matrix may have leftover cells. - Using recursion to fill the spiral: with up to 10^5 cells a recursive fill risks a stack overflow.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.