Spiral Matrix III - Practice Coding Problems

Spiral Matrix III - Problem

You start at cell (rStart, cStart) of an rows × cols grid facing east. The northwest corner is at the first row and column in the grid, and the southeast corner is at the last row and column.

You will walk in a clockwise spiral shape to visit every position in this grid. Whenever you move outside the grid's boundary, we continue our walk outside the grid (but may return to the grid boundary later).

Eventually, we reach all rows × cols spaces of the grid. Return an array of coordinates representing the positions of the grid in the order you visited them.

Input & Output

Example 1 — Small 2×2 Grid

$ Input: rows = 1, cols = 4, rStart = 0, cStart = 0

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

💡 Note: Start at (0,0), walk east: (0,0)→(0,1)→(0,2)→(0,3). All positions are in-bounds and visited in spiral order.

Example 2 — Square Grid Starting Center

$ Input: rows = 5, cols = 6, rStart = 1, cStart = 4

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

💡 Note: Start at (1,4), spiral outward: 1 east, 1 south, 2 west, 2 north, 3 east, etc. Only record positions within the 5×6 grid bounds.

Example 3 — Single Cell Grid

$ Input: rows = 1, cols = 1, rStart = 0, cStart = 0

› Output: [[0,0]]

💡 Note: Edge case: only one cell exists, so return that single position.

Constraints

1 ≤ rows, cols ≤ 100
0 ≤ rStart < rows
0 ≤ cStart < cols

Visualization

Tap to expand

Understanding the Visualization

Input Grid

rows=1, cols=4, start at (0,0)

Spiral Walk

Walk east: (0,0)→(0,1)→(0,2)→(0,3)

Result Array

Return coordinates in visit order: [[0,0],[0,1],[0,2],[0,3]]

Key Takeaway

🎯 Key Insight: Simulate clockwise spiral with increasing step pattern (1,1,2,2,3,3...) and record only in-bounds positions

Asked in

G Google 15 a Amazon 12 M Microsoft 8 f Facebook 6

The key insight is to simulate the clockwise spiral pattern with increasing step counts: 1,1,2,2,3,3... The optimal simulation approach follows the spiral movement and only records positions within grid bounds. Time: O(max(rows,cols)²), Space: O(rows×cols)

Common Approaches

Approach	Time	Space	Notes
✓ Simulation - Follow Spiral Pattern	O(max(rows, cols)²)	O(rows × cols)	Simulate the clockwise spiral movement with direction changes and step counting
Brute Force - Try All Paths	O(4^(rows×cols))	O(rows×cols)	Try all possible walking paths and find one that visits all grid cells

Simulation - Follow Spiral Pattern — Algorithm Steps

Start at (rStart, cStart) facing east
Move in current direction for 'steps' count
Turn clockwise (east→south→west→north→east)
Increase step count every 2 turns
Record only valid grid positions

Visualization

Tap to expand

Step-by-Step Walkthrough

Start

Begin at (rStart, cStart) facing east

Walk Pattern

Steps: 1 east, 1 south, 2 west, 2 north, 3 east...

Record Valid

Only record positions within grid bounds

Code -

solution.c — C

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

int** solution(int rows, int cols, int rStart, int cStart, int* returnSize) {
    int** result = (int**)malloc(rows * cols * sizeof(int*));
    int visited[rows][cols];
    memset(visited, 0, sizeof(visited));
    
    int directions[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}; // east, south, west, north
    int count = 0;
    
    int r = rStart, c = cStart;
    result[count] = (int*)malloc(2 * sizeof(int));
    result[count][0] = r;
    result[count][1] = c;
    visited[r][c] = 1;
    count++;
    
    if (rows * cols == 1) {
        *returnSize = 1;
        return result;
    }
    
    int steps = 1;
    int direction = 0; // start facing east
    
    while (count < rows * cols) {
        for (int i = 0; i < 2; i++) { // each step count is used for 2 directions
            int dr = directions[direction][0];
            int dc = directions[direction][1];
            for (int j = 0; j < steps; j++) {
                r += dr;
                c += dc;
                // only add if within grid bounds and not visited
                if (r >= 0 && r < rows && c >= 0 && c < cols && !visited[r][c]) {
                    result[count] = (int*)malloc(2 * sizeof(int));
                    result[count][0] = r;
                    result[count][1] = c;
                    visited[r][c] = 1;
                    count++;
                }
            }
            direction = (direction + 1) % 4; // turn clockwise
            if (count == rows * cols) break;
        }
        steps++; // increase step count after every 2 direction changes
    }
    
    *returnSize = count;
    return result;
}

int main() {
    int rows, cols, rStart, cStart;
    scanf("%d %d %d %d", &rows, &cols, &rStart, &cStart);
    
    int returnSize;
    int** result = solution(rows, cols, rStart, cStart, &returnSize);
    
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        printf("[%d,%d]", result[i][0], result[i][1]);
        if (i < returnSize - 1) printf(",");
        free(result[i]);
    }
    printf("]\n");
    free(result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(max(rows, cols)²)

Spiral expands until it covers the entire grid area

✓ Linear Growth

Space Complexity

O(rows × cols)

Store result array with all grid positions and visited set

✓ Linear Space

35.4K Views

Medium Frequency

~25 min Avg. Time

892 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

Simulation - Follow Spiral Pattern — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler