Spiral Matrix IV

medium linked list matrix simulation spiral

Problem

Given dimensions m and n and the head of a linked list, build an m × n matrix filled with the list values in clockwise spiral order, starting from the top-left. Any cells left over after the list is exhausted are filled with -1. Return the matrix.

Inputm = 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]]

The 13 values spiral inward; the two central cells stay empty and become -1.

Inputm = 1, n = 4, head = [0,1,2]

Output[[0,1,2,-1]]

A single row fills left to right; the last cell has no value, so it becomes -1.

m (rows)

n (cols)

head (comma-separated)

def spiral_matrix(m, n, head):
    grid = [[-1] * n for _ in range(m)]
    top, bottom, left, right = 0, m - 1, 0, n - 1
    while head and top <= bottom and left <= right:
        for c in range(left, right + 1):
            if not head: break
            grid[top][c] = head.val; head = head.next
        top += 1
        for r in range(top, bottom + 1):
            if not head: break
            grid[r][right] = head.val; head = head.next
        right -= 1
        for c in range(right, left - 1, -1):
            if not head: break
            grid[bottom][c] = head.val; head = head.next
        bottom -= 1
        for r in range(bottom, top - 1, -1):
            if not head: break
            grid[r][left] = head.val; head = head.next
        left += 1
    return grid

function spiralMatrix(m, n, head) {
  const grid = Array.from({ length: m }, () => Array(n).fill(-1));
  let top = 0, bottom = m - 1, left = 0, right = n - 1;
  while (head && top <= bottom && left <= right) {
    for (let c = left; c <= right && head; c++) {
      grid[top][c] = head.val; head = head.next;
    }
    top++;
    for (let r = top; r <= bottom && head; r++) {
      grid[r][right] = head.val; head = head.next;
    }
    right--;
    for (let c = right; c >= left && head; c--) {
      grid[bottom][c] = head.val; head = head.next;
    }
    bottom--;
    for (let r = bottom; r >= top && head; r--) {
      grid[r][left] = head.val; head = head.next;
    }
    left++;
  }
  return grid;
}

int[][] spiralMatrix(int m, int n, ListNode head) {
    int[][] grid = new int[m][n];
    for (int[] row : grid) Arrays.fill(row, -1);
    int top = 0, bottom = m - 1, left = 0, right = n - 1;
    while (head != null && top <= bottom && left <= right) {
        for (int c = left; c <= right && head != null; c++) {
            grid[top][c] = head.val; head = head.next;
        }
        top++;
        for (int r = top; r <= bottom && head != null; r++) {
            grid[r][right] = head.val; head = head.next;
        }
        right--;
        for (int c = right; c >= left && head != null; c--) {
            grid[bottom][c] = head.val; head = head.next;
        }
        bottom--;
        for (int r = bottom; r >= top && head != null; r--) {
            grid[r][left] = head.val; head = head.next;
        }
        left++;
    }
    return grid;
}

vector<vector<int>> spiralMatrix(int m, int n, ListNode* head) {
    vector<vector<int>> grid(m, vector<int>(n, -1));
    int top = 0, bottom = m - 1, left = 0, right = n - 1;
    while (head && top <= bottom && left <= right) {
        for (int c = left; c <= right && head; c++) {
            grid[top][c] = head->val; head = head->next;
        }
        top++;
        for (int r = top; r <= bottom && head; r++) {
            grid[r][right] = head->val; head = head->next;
        }
        right--;
        for (int c = right; c >= left && head; c--) {
            grid[bottom][c] = head->val; head = head->next;
        }
        bottom--;
        for (int r = bottom; r >= top && head; r--) {
            grid[r][left] = head->val; head = head->next;
        }
        left++;
    }
    return grid;
}

Explanation

The trick is to not compute spiral coordinates with clever modular math. Instead we keep four boundary pointers — top, bottom, left, right — that mark the outer ring of cells still to be filled, and we shrink them as each side is consumed.

We start with the matrix pre-filled with -1, so if the list runs out we simply stop and every untouched cell already holds the pad value. No special end-handling is needed.

Each pass of the while loop walks one full ring clockwise: left→right along the top row, then top→bottom down the right column, then right→left along the bottom row, then bottom→top up the left column. After finishing each side we move its boundary inward (top++, right--, bottom--, left++).

Every inner loop also checks that the list still has nodes (head is not null) before writing, and advances head = head.next after writing. The moment head becomes null we break out, leaving the remaining cells as -1.

Because boundaries only ever close in, we visit each of the m·n cells at most once, giving linear time. The single output matrix is the only extra space.

Time: O(m · n) Space: O(m · n)