Problem Description

Given the dimensions of a grid, rows and cols, and a starting cell at position (rStart, cStart), you are to return the coordinates of all cells in the grid in the order you would visit them while walking in a spiral pattern. The spiral starts at the given cell and expands outward in the order: right, down, left, up, and repeats, always increasing the step size every two turns.

The output should be a list of coordinates [row, col] for every cell in the grid, in the order they are first visited by the spiral. Each cell must be visited exactly once, and you must not revisit or skip any cell.

Constraints:

• 1 <= rows, cols <= 100
• 0 <= rStart < rows
• 0 <= cStart < cols
• There is only one valid spiral traversal for any input.

Thought Process

The problem asks us to simulate a spiral traversal of a 2D grid starting from a specific cell. The naive approach would be to simulate every possible direction and check boundaries at every step, but this could get complicated and inefficient if not structured well.

A more systematic way is to recognize that the spiral pattern consists of repeated cycles: move right for n steps, down for n steps, left for n+1 steps, up for n+1 steps, and so on, increasing the number of steps after every two directions (i.e., after a full right-down or left-up cycle).

Instead of visiting every cell and marking them, we can just simulate the spiral, and only record positions that are within bounds. This avoids unnecessary checks and makes the process more efficient and easier to reason about.

Solution Approach

Let's break down the algorithm step-by-step:

1. Initialization:
   • Start at (rStart, cStart)
   • Prepare a result list to store visited coordinates.
   • Set up direction vectors for right, down, left, and up (in that order).
   • Set a variable to track the current step size, starting at 1.
2. Spiral Simulation:
   • While the result list has fewer than rows * cols cells, repeat:
   • For each direction (right, down, left, up):
   • For the current step size, move in that direction, one step at a time.
   • For each step, if the current position is inside the grid, add it to the result.
   • After every two directions, increment the step size by 1.
3. Termination:
   • Stop when all cells have been visited and added to the result list.

This approach is efficient because it only checks each cell once and does not require marking or revisiting cells. The direction vectors and systematic step size increment make the traversal predictable and easy to implement.

Example Walkthrough

Let's walk through an example with rows = 3, cols = 3, rStart = 1, cStart = 1:

1. Start at (1, 1): Add [1, 1] to the result.
2. First cycle (step size = 1):
   • Right: Move to (1, 2) (add to result)
   • Down: Move to (2, 2) (add to result)
   Increase step size to 2.
3. Second cycle (step size = 2):
   • Left: Move to (2, 1) (add), then (2, 0) (add)
   • Up: Move to (1, 0) (add), then (0, 0) (add)
   Increase step size to 3.
4. Third cycle (step size = 3):
   • Right: Move to (0, 1) (add), then (0, 2) (add), then (-1, 2) (out of bounds, skip)
   • Down: Move to (1, 2) (already visited), (2, 2) (already visited), (3, 2) (out of bounds, skip)
5. Result: All 9 cells have been visited in spiral order: [[1,1],[1,2],[2,2],[2,1],[2,0],[1,0],[0,0],[0,1],[0,2]]

Time and Space Complexity

Brute-force approach: If we tried to simulate the entire grid and check every cell at every step, the time complexity could be much higher, possibly O((rows * cols)^2) if not careful.

Optimized spiral simulation:

• Time Complexity: O(rows * cols) — Every cell is visited exactly once.
• Space Complexity: O(rows * cols) — The result list stores every cell's coordinates.

Summary

The spiral matrix traversal problem can be solved elegantly by simulating the spiral motion with controlled direction changes and step sizes. By incrementing the number of steps after every two directions and only recording valid in-bounds cells, we avoid unnecessary computation and ensure every cell is visited exactly once. This approach is efficient, systematic, and leverages the predictable nature of spiral movement to produce a clean solution.

Code Implementation

class Solution:
    def spiralMatrixIII(self, rows, cols, rStart, cStart):
        res = []
        total = rows * cols
        res.append([rStart, cStart])
        steps = 1
        dirs = [(0,1), (1,0), (0,-1), (-1,0)]  # right, down, left, up
        r, c = rStart, cStart
        while len(res) < total:
            for i in range(4):
                dr, dc = dirs[i]
                for _ in range(steps):
                    r += dr
                    c += dc
                    if 0 <= r < rows and 0 <= c < cols:
                        res.append([r, c])
                if i % 2 == 1:
                    steps += 1
        return res
      

class Solution {
public:
    vector<vector<int>> spiralMatrixIII(int rows, int cols, int rStart, int cStart) {
        vector<vector<int>> res;
        int total = rows * cols;
        res.push_back({rStart, cStart});
        int steps = 1;
        int dirs[4][2] = {{0,1}, {1,0}, {0,-1}, {-1,0}};
        int r = rStart, c = cStart;
        while (res.size() < total) {
            for (int i = 0; i < 4; ++i) {
                for (int j = 0; j < steps; ++j) {
                    r += dirs[i][0];
                    c += dirs[i][1];
                    if (r >= 0 && r < rows && c >= 0 && c < cols) {
                        res.push_back({r, c});
                    }
                }
                if (i % 2 == 1) steps++;
            }
        }
        return res;
    }
};
      

class Solution {
    public int[][] spiralMatrixIII(int rows, int cols, int rStart, int cStart) {
        int[][] res = new int[rows * cols][2];
        int idx = 0;
        res[idx++] = new int[]{rStart, cStart};
        int steps = 1;
        int[][] dirs = {{0,1},{1,0},{0,-1},{-1,0}};
        int r = rStart, c = cStart;
        while (idx < rows * cols) {
            for (int i = 0; i < 4; ++i) {
                for (int j = 0; j < steps; ++j) {
                    r += dirs[i][0];
                    c += dirs[i][1];
                    if (r >= 0 && r < rows && c >= 0 && c < cols) {
                        res[idx++] = new int[]{r, c};
                    }
                }
                if (i % 2 == 1) steps++;
            }
        }
        return res;
    }
}
      

var spiralMatrixIII = function(rows, cols, rStart, cStart) {
    let res = [[rStart, cStart]];
    let total = rows * cols;
    let steps = 1;
    let dirs = [[0,1], [1,0], [0,-1], [-1,0]];
    let r = rStart, c = cStart;
    while (res.length < total) {
        for (let i = 0; i < 4; ++i) {
            let [dr, dc] = dirs[i];
            for (let j = 0; j < steps; ++j) {
                r += dr;
                c += dc;
                if (r >= 0 && r < rows && c >= 0 && c < cols) {
                    res.push([r, c]);
                }
            }
            if (i % 2 === 1) steps++;
        }
    }
    return res;
};