Spiral Matrix IV

Medium
2023.

Spiral Matrix IV

Spiral Matrix IV is a medium coding problem on arrays, matrix and simulation, asked in Amazon interviews.

You are given two integers m and n, the dimensions of a matrix, and the head of a linked list of integers.

Build an m x n matrix by writing the list's values in spiral order, clockwise, starting from the top-left cell: along the top row to the right, down the right column, back along the bottom row, up the left column, and inwards. If the list runs out before the matrix is full, every remaining cell holds -1.

Return the matrix.

Example 1

Input
m = 3, n = 4, head = [1,2,3,4,5,6,7,8,9]
Output
[[1,2,3,4],[-1,-1,-1,5],[9,8,7,6]]
Explanation
The top row takes 1–4, the right column 5 and 6, the bottom row 7, 8, 9 leftwards. The two middle cells are never reached and stay -1.

Example 2

Input
m = 1, n = 4, head = [0,1,2]
Output
[[0,1,2,-1]]
Explanation
A single row is filled left to right; the last cell gets -1.

Example 3

Input
m = 2, n = 2, head = [5,6,7,8]
Output
[[5,6],[8,7]]
Explanation
The spiral turns at every corner of the 2 x 2 matrix.

Constraints

  • 1 <= m, n <= 10^5
  • 1 <= m * n <= 10^5
  • The number of nodes in the list is in the range [1, m * n]
  • 0 <= Node.val <= 1000
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * Definition for singly-linked list (provided by the judge — do not redefine it):
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {number} m
 * @param {number} n
 * @param {ListNode} head
 * @return {number[][]}
 */
var spiralMatrix = function(m, n, head) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Spiral Matrix IV — Solution in Python, Java & C++

Spiral Matrix IV solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem, asked at Amazon.

Spiral Matrix IV is a medium coding problem on arrays, matrix and simulation, asked in Amazon interviews.

  • Difficulty: Medium
  • Topics: Arrays, Matrix, Simulation
  • Asked at: Amazon
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

You are given two integers m and n, the dimensions of a matrix, and the head of a linked list of integers.

Build an m x n matrix by writing the list's values in spiral order, clockwise, starting from the top-left cell: along the top row to the right, down the right column, back along the bottom row, up the left column, and inwards. If the list runs out before the matrix is full, every remaining cell holds -1.

Return the matrix.

Example 1

Input: m = 3, n = 4, head = [1,2,3,4,5,6,7,8,9]
Output: [[1,2,3,4],[-1,-1,-1,5],[9,8,7,6]]
Explanation: The top row takes 1–4, the right column 5 and 6, the bottom row 7, 8, 9 leftwards. The two middle cells are never reached and stay -1.

Example 2

Input: m = 1, n = 4, head = [0,1,2]
Output: [[0,1,2,-1]]
Explanation: A single row is filled left to right; the last cell gets -1.

Example 3

Input: m = 2, n = 2, head = [5,6,7,8]
Output: [[5,6],[8,7]]
Explanation: The spiral turns at every corner of the 2 x 2 matrix.

Constraints

  • 1 <= m, n <= 10^5
  • 1 <= m * n <= 10^5
  • The number of nodes in the list is in the range [1, m * n]
  • 0 <= Node.val <= 1000

Hints for Spiral Matrix IV

  1. Hint 1

    Start with every cell set to -1; then you only have to place the list's values.

  2. Hint 2

    Walk the matrix with a position and a direction (right, down, left, up), placing one value per step.

  3. Hint 3

    Turn clockwise whenever the next cell would leave the matrix or is already filled — node values are never negative, so -1 doubles as "not filled yet".

How to solve Spiral Matrix IV

Simulate the spiral directly: keep the current cell and direction, write the next list value, and turn clockwise when the step ahead is blocked by the border or a written cell.

Approach

  1. Create the m x n matrix filled with -1; set r = c = 0 and the direction to right.
  2. For each node: write its value at (r, c), then look at the next cell in the current direction.
  3. If that cell is outside the matrix or not -1, rotate the direction clockwise (right → down → left → up → right) and recompute the next cell.
  4. Move to it and continue with the next node. Return the matrix when the list ends.

Why it works

The spiral is exactly the path that goes straight until blocked and then turns right. Written cells block exactly like a border, so one turn per blocked step reproduces the spiral ring by ring, and since the list has at most m * n values the walk never needs a cell that does not exist.

Complexity

  • Time — O(m * n)
  • Space — O(1) besides the output

Pitfalls

  • Using 0 as the empty marker breaks on lists that contain 0; -1 is safe because values are non-negative.
  • After the last value the computed next step may point outside the matrix — just never use it.

Reference solution

Python

from typing import List, Optional

def spiralMatrix(m: int, n: int, head: Optional[ListNode]) -> List[List[int]]:
    mat = [[-1] * n for _ in range(m)]
    dr, dc = (0, 1, 0, -1), (1, 0, -1, 0)
    r = c = d = 0
    while head:
        mat[r][c] = head.val
        nr, nc = r + dr[d], c + dc[d]
        if not (0 <= nr < m and 0 <= nc < n) or mat[nr][nc] != -1:
            d = (d + 1) % 4
            nr, nc = r + dr[d], c + dc[d]
        r, c = nr, nc
        head = head.next
    return mat

Java

public static int[][] spiralMatrix(int m, int n, ListNode head) {
    int[][] mat = new int[m][n];
    for (int[] row : mat) Arrays.fill(row, -1);
    int[] dr = {0, 1, 0, -1}, dc = {1, 0, -1, 0};
    int r = 0, c = 0, d = 0;
    for (; head != null; head = head.next) {
        mat[r][c] = head.val;
        int nr = r + dr[d], nc = c + dc[d];
        if (nr < 0 || nr >= m || nc < 0 || nc >= n || mat[nr][nc] != -1) { d = (d + 1) % 4; nr = r + dr[d]; nc = c + dc[d]; }
        r = nr; c = nc;
    }
    return mat;
}

C++

vector<vector<int>> spiralMatrix(int m, int n, ListNode* head) {
    vector<vector<int>> mat(m, vector<int>(n, -1));
    int dr[4] = {0, 1, 0, -1}, dc[4] = {1, 0, -1, 0};
    int r = 0, c = 0, d = 0;
    for (; head; head = head->next) {
        mat[r][c] = head->val;
        int nr = r + dr[d], nc = c + dc[d];
        if (nr < 0 || nr >= m || nc < 0 || nc >= n || mat[nr][nc] != -1) { d = (d + 1) % 4; nr = r + dr[d]; nc = c + dc[d]; }
        r = nr; c = nc;
    }
    return mat;
}

JavaScript

var spiralMatrix = function(m, n, head) {
    var mat = [];
    for (var i = 0; i < m; i++) { mat.push([]); for (var j = 0; j < n; j++) mat[i].push(-1); }
    var dr = [0, 1, 0, -1], dc = [1, 0, -1, 0];
    var r = 0, c = 0, d = 0;
    for (; head !== null; head = head.next) {
        mat[r][c] = head.val;
        var nr = r + dr[d], nc = c + dc[d];
        if (nr < 0 || nr >= m || nc < 0 || nc >= n || mat[nr][nc] !== -1) { d = (d + 1) % 4; nr = r + dr[d]; nc = c + dc[d]; }
        r = nr; c = nc;
    }
    return mat;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Matrix and Grid Traversal