Spiral Matrix III

medium array matrix simulation

Problem

You start at cell (rStart, cStart) of a rows × cols grid facing east. Walk in a clockwise spiral, visiting cells one step at a time, and whenever a step lands inside the grid record that coordinate. Return all rows × cols coordinates in the order you visit them.

Inputrows = 1, cols = 4, rStart = 0, cStart = 0

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

From the only row we keep walking east; off-grid steps in other directions are skipped.

rows

cols

rStart

cStart

def spiral_matrix_iii(rows, cols, rStart, cStart):
    dirs = [(0, 1), (1, 0), (0, -1), (-1, 0)]  # E, S, W, N
    res = [[rStart, cStart]]
    r, c, d, step = rStart, cStart, 0, 1
    while len(res) < rows * cols:
        for _ in range(2):
            dr, dc = dirs[d]
            for _ in range(step):
                r, c = r + dr, c + dc
                if 0 <= r < rows and 0 <= c < cols:
                    res.append([r, c])
            d = (d + 1) % 4
        step += 1
    return res

function spiralMatrixIII(rows, cols, rStart, cStart) {
  const dirs = [[0, 1], [1, 0], [0, -1], [-1, 0]]; // E, S, W, N
  const res = [[rStart, cStart]];
  let r = rStart, c = cStart, d = 0, step = 1;
  while (res.length < rows * cols) {
    for (let t = 0; t < 2; t++) {
      const [dr, dc] = dirs[d];
      for (let k = 0; k < step; k++) {
        r += dr; c += dc;
        if (r >= 0 && r < rows && c >= 0 && c < cols) res.push([r, c]);
      }
      d = (d + 1) % 4;
    }
    step++;
  }
  return res;
}

class Solution {
    public int[][] spiralMatrixIII(int rows, int cols, int rStart, int cStart) {
        int[][] dirs = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}; // E, S, W, N
        int[][] res = new int[rows * cols][2];
        int idx = 0;
        res[idx++] = new int[]{rStart, cStart};
        int r = rStart, c = cStart, d = 0, step = 1;
        while (idx < rows * cols) {
            for (int t = 0; t < 2; t++) {
                int dr = dirs[d][0], dc = dirs[d][1];
                for (int k = 0; k < step; k++) {
                    r += dr; c += dc;
                    if (r >= 0 && r < rows && c >= 0 && c < cols) res[idx++] = new int[]{r, c};
                }
                d = (d + 1) % 4;
            }
            step++;
        }
        return res;
    }
}

vector<vector<int>> spiralMatrixIII(int rows, int cols, int rStart, int cStart) {
    int dirs[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}; // E, S, W, N
    vector<vector<int>> res = {{rStart, cStart}};
    int r = rStart, c = cStart, d = 0, step = 1;
    while ((int)res.size() < rows * cols) {
        for (int t = 0; t < 2; t++) {
            int dr = dirs[d][0], dc = dirs[d][1];
            for (int k = 0; k < step; k++) {
                r += dr; c += dc;
                if (r >= 0 && r < rows && c >= 0 && c < cols) res.push_back({r, c});
            }
            d = (d + 1) % 4;
        }
        step++;
    }
    return res;
}

Explanation

The starting cell may be anywhere, even off-center, so the spiral often pokes outside the grid. The trick is to walk the full clockwise spiral anyway and simply record only the steps that land inside the grid.

We cycle through four directions in order East, South, West, North using dirs. The pattern of an outward spiral is special: the run lengths go 1, 1, 2, 2, 3, 3, …. So we walk step cells, turn, walk step cells, turn, then increase step.

That is exactly what the for _ in range(2) loop does — two turns at the same step length — after which step += 1 grows the spiral. After each single move we check 0 <= r < rows and 0 <= c < cols and append the coordinate to res only if it is in bounds.

We keep going until res holds all rows * cols cells, which is guaranteed because an ever-growing spiral eventually covers the whole grid.

Example: rows=1, cols=4 starting at (0,0). Walking east stays in the single row and collects (0,1),(0,2),(0,3); the south/west/north steps fall off-grid and are skipped, giving [[0,0],[0,1],[0,2],[0,3]].

Time: O(max(rows, cols)²) Space: O(rows · cols)