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^51 <= m * n <= 10^5The number of nodes in the list is in the range [1, m * n]0 <= Node.val <= 1000
Hints for Spiral Matrix IV
Hint 1
Start with every cell set to
-1; then you only have to place the list's values.Hint 2
Walk the matrix with a position and a direction (right, down, left, up), placing one value per step.
Hint 3
Turn clockwise whenever the next cell would leave the matrix or is already filled — node values are never negative, so
-1doubles 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
- Create the
m x nmatrix filled with-1; setr = c = 0and the direction to right. - For each node: write its value at
(r, c), then look at the next cell in the current direction. - If that cell is outside the matrix or not
-1, rotate the direction clockwise (right → down → left → up → right) and recompute the next cell. - 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
0as the empty marker breaks on lists that contain0;-1is 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 matJava
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