Spiral Matrix IV - Practice Coding Problems

Spiral Matrix IV - Problem

Welcome to one of the most elegant matrix problems! 🌪️ You're tasked with creating a spiral matrix that combines linked list traversal with matrix manipulation.

Given:

Dimensions: Two integers m and n representing matrix size
Data source: Head of a linked list containing integers

Your mission: Generate an m × n matrix by placing linked list values in clockwise spiral order, starting from the top-left corner. Think of it as drawing a spiral from outside to inside!

🎯 Special rule: If you run out of linked list values before filling the entire matrix, fill remaining positions with -1.

Example: With a 3×3 matrix and linked list [3,0,2,6,8,1,7,9,4,2,5,5,0], you'd spiral clockwise: right → down → left → up → repeat until the center is reached.

Input & Output

example_1.py — Basic Spiral

$ 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]]

💡 Note: Starting from top-left, we spiral clockwise: first row (3→0→2→6→8), then right column (1→7), bottom row (9→4→2→5), left column (5), and finally the remaining center positions with linked list values or -1.

example_2.py — Perfect Fit

$ Input: m = 1, n = 4, head = [0,1,2]

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

💡 Note: Single row matrix: fill left to right with linked list values [0,1,2], then pad remaining position with -1.

example_3.py — Excess Values

$ Input: m = 2, n = 2, head = [1,2,3,4,5,6,7,8]

› Output: [[1,2],[4,3]]

💡 Note: 2×2 matrix filled in spiral order: (0,0)→1, (0,1)→2, (1,1)→3, (1,0)→4. Extra linked list values (5,6,7,8) are ignored since matrix is full.

Constraints

1 ≤ m, n ≤ 10⁵
1 ≤ m × n ≤ 10⁵
The number of nodes in the list is in the range [1, m × n]
0 ≤ Node.val ≤ 1000

Visualization

Tap to expand

Understanding the Visualization

Plant the Perimeter

Start at the northwest corner, plant along the north border (top row)

Move Down the East Side

Turn clockwise, plant down the east border (right column)

Cross the South Border

Turn clockwise again, plant across the south border (bottom row, right to left)

Up the West Side

Final turn, plant up the west border (left column, bottom to top)

Spiral Inward

Repeat the pattern for inner layers until the garden center is reached or flowers run out

Key Takeaway

🎯 Key Insight: By maintaining shrinking boundaries instead of checking individual positions, we create an elegant and efficient spiral traversal that mirrors natural growth patterns.

Asked in

G Google 85 f Meta 72 a Amazon 68 ⊞ Microsoft 45

The optimal solution uses a boundary-shrinking approach with O(m×n) time complexity. We maintain four boundaries (top, bottom, left, right) and systematically fill each layer of the spiral, shrinking boundaries after completing each side. This eliminates the need for direction checking and provides cleaner, more efficient code than the naive approach.

Common Approaches

Approach	Time	Space	Notes
✓ Direction Tracking with Boundary Checks	O(m×n)	O(m×n)	Track current position and direction, check boundaries and visited cells at each step
Layer-by-Layer Boundary Approach (Optimal)	O(m×n)	O(m×n)	Track four boundaries and shrink them as we complete each spiral layer

Direction Tracking with Boundary Checks — Algorithm Steps

Initialize result matrix with -1 values
Start at position (0,0) going RIGHT
For each linked list node, place value at current position
Try to move in current direction
If blocked (boundary/filled cell), turn clockwise
Continue until linked list is exhausted

Visualization

Tap to expand

Step-by-Step Walkthrough

Start Position

Begin at (0,0) facing RIGHT with first linked list value

Move Forward

Continue in current direction while path is clear

Hit Boundary

Detect boundary or filled cell, turn clockwise

Continue Spiral

Repeat until linked list is exhausted

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct ListNode {
    int val;
    struct ListNode *next;
};

int** spiralMatrix(int m, int n, struct ListNode* head, int* returnSize, int** returnColumnSizes) {
    *returnSize = m;
    *returnColumnSizes = (int*)malloc(m * sizeof(int));
    
    int** matrix = (int**)malloc(m * sizeof(int*));
    for (int i = 0; i < m; i++) {
        matrix[i] = (int*)malloc(n * sizeof(int));
        (*returnColumnSizes)[i] = n;
        for (int j = 0; j < n; j++) {
            matrix[i][j] = -1;
        }
    }
    
    // Direction vectors: right, down, left, up
    int directions[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
    int currentDir = 0;
    
    int row = 0, col = 0;
    struct ListNode* current = head;
    
    while (current) {
        matrix[row][col] = current->val;
        current = current->next;
        
        if (!current) break;
        
        // Calculate next position
        int dr = directions[currentDir][0];
        int dc = directions[currentDir][1];
        int nextRow = row + dr, nextCol = col + dc;
        
        // Check if we need to turn
        if (nextRow < 0 || nextRow >= m || 
            nextCol < 0 || nextCol >= n || 
            matrix[nextRow][nextCol] != -1) {
            currentDir = (currentDir + 1) % 4;
            dr = directions[currentDir][0];
            dc = directions[currentDir][1];
            nextRow = row + dr;
            nextCol = col + dc;
        }
        
        row = nextRow;
        col = nextCol;
    }
    
    return matrix;
}

int main() {
    int m, n;
    scanf("%d %d", &m, &n);
    
    char line[10000];
    fgets(line, sizeof(line), stdin); // consume newline
    fgets(line, sizeof(line), stdin);
    
    struct ListNode* head = NULL;
    struct ListNode* current = NULL;
    
    char* token = strtok(line, " \n");
    while (token) {
        int val = atoi(token);
        if (!head) {
            head = (struct ListNode*)malloc(sizeof(struct ListNode));
            head->val = val;
            head->next = NULL;
            current = head;
        } else {
            current->next = (struct ListNode*)malloc(sizeof(struct ListNode));
            current->next->val = val;
            current->next->next = NULL;
            current = current->next;
        }
        token = strtok(NULL, " \n");
    }
    
    int returnSize;
    int* returnColumnSizes;
    int** result = spiralMatrix(m, n, head, &returnSize, &returnColumnSizes);
    
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        printf("[");
        for (int j = 0; j < returnColumnSizes[i]; j++) {
            printf("%d", result[i][j]);
            if (j < returnColumnSizes[i] - 1) printf(",");
        }
        printf("]");
        if (i < returnSize - 1) printf(",");
    }
    printf("]\n");
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(m×n)

We visit each cell exactly once, and for each cell we do constant work

✓ Linear Growth

Space Complexity

O(m×n)

Space for the result matrix, plus O(min(m,n,L)) for recursion/iteration where L is linked list length

⚡ Linearithmic Space

25.0K Views

Medium Frequency

~15 min Avg. Time

850 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Direction Tracking with Boundary Checks — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler