# Spiral Matrix III
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/spiral-matrix-iii)
Canonical: https://scaleengineer.com/dsa/problems/spiral-matrix-iii
**Data structures:** Array, Matrix
**Companies:** [Dataminr](https://scaleengineer.com/companies/dataminr)
---
## Problem
You start at the cell `(rStart, cStart)` of an `rows x 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_.

**Example 1:**

![](https://assets.glich.co/dsa/spiral-matrix-iii/image0.png) 

**Input:** rows = 1, cols = 4, rStart = 0, cStart = 0
**Output:** [[0,0],[0,1],[0,2],[0,3]]

**Example 2:**

![](https://assets.glich.co/dsa/spiral-matrix-iii/image1.png) 

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

**Constraints:**

* `1 <= rows, cols <= 100`
* `0 <= rStart < rows`
* `0 <= cStart < cols`

# Approaches
## Mathematical Calculation and Sorting
This approach avoids simulating the spiral path step-by-step. Instead, for every cell `(r, c)` in the grid, we mathematically calculate its visiting order in the spiral sequence. After computing this order for all `rows * cols` cells, we sort the cells based on this order and return the sorted coordinates.
**Time:** O(rows * cols * log(rows * cols))

The main operations are iterating through all `rows * cols` cells and then sorting them. Calculating the order for each cell is an O(1) operation. The dominant factor is the sort, leading to a time complexity of `O(N log N)` where `N = rows * cols`. · **Space:** O(rows * cols)

We need to store the coordinates and their calculated order for all `rows * cols` cells before sorting. This requires space proportional to the size of the grid.
**Pros:** Represents a different, analytical way of solving the problem.; Can be more efficient than simulation for grids with a very high aspect ratio (i.e., very long and thin grids).
**Cons:** The primary drawback is the complexity of deriving and implementing the mathematical formulas for the spiral order. It's highly error-prone.; For square-like grids, where `rows` and `cols` are similar, the `O(R*C*log(R*C))` time complexity is generally worse than the simulation approach's `O(max(R,C)^2)`.; The logic is less intuitive and harder to debug compared to a direct simulation.
### Explanation
The core idea is to find a closed-form expression for the number of steps required to reach any given cell `(r, c)` from the starting cell `(rStart, cStart)`. We can analyze the geometry of the spiral path. The path forms expanding layers around the start point. A cell at a relative position `(dr, dc) = (r - rStart, c - cStart)` lies on the `k`-th layer, where `k = max(|dr|, |dc|)`. By deriving formulas for the total steps to reach the corners of each layer, we can pinpoint the exact step count for any cell on that layer's boundary. Once we have a function `getOrder(r, c)` that returns the spiral order, we can apply it to all cells in the grid, store these `(order, coordinate)` pairs, and sort them to get the final path. While elegant in theory, this method is complex to implement correctly due to the irregular step increases (1, 1, 2, 2, 3, 3, ...).
### Algorithm
1. Create a list or array to hold cell information, specifically `(order, r, c)`.
2. Iterate through every cell `(r, c)` in the `rows x cols` grid.
3. For each cell, calculate its position (`order`) in the spiral sequence using a mathematical formula. This involves:
    a. Finding the cell's coordinates `(dr, dc)` relative to the start `(rStart, cStart)`.
    b. Determining the spiral layer `k = max(|dr|, |dc|)` the cell belongs to.
    c. Using pre-derived formulas for the number of steps to reach the corners of layer `k` to find the base step count.
    d. Adding an offset based on the cell's position along its specific segment (East, South, West, or North) of the layer.
4. Store the calculated `order` along with the cell's coordinates `(r, c)`.
5. After calculating the order for all cells, sort the list of cells based on their `order`.
6. Create the final `int[][]` result array and populate it with the coordinates from the sorted list.

## Direct Simulation
This approach directly simulates the spiral walk. Starting from `(rStart, cStart)`, we move in an expanding clockwise spiral, one step at a time. At each step, we check if the new coordinate is within the grid's boundaries. If it is, we add it to our result list. We continue this process until we have collected all `rows * cols` coordinates of the grid.
**Time:** O(max(rows, cols)^2)

The spiral walk continues until all `rows * cols` cells are found. The path covers an expanding square-like area. To cover a grid of size `rows x cols`, the spiral might have to extend up to `max(rows, cols)` distance from the start in any direction. The number of steps simulated is proportional to the area of a square with side length `2 * max(rows, cols)`, which gives a time complexity of `O(max(rows, cols)^2)`. · **Space:** O(1) (excluding output array)

The simulation only requires a few variables to keep track of the current state (position, direction, length), resulting in constant extra space. The `O(rows * cols)` space is for the result array, which is typically not counted as extra space.
**Pros:** Simple and intuitive to understand and implement.; Directly generates the coordinates in the correct order, avoiding complex calculations or sorting.; Generally more performant than the mathematical approach for square-like grids and within the given constraints.
**Cons:** For grids with a very high aspect ratio (e.g., 1x100 or 100x1), this approach might perform more steps than necessary compared to the mathematical approach.
### Explanation
We can trace the spiral path by keeping track of our current position `(r, c)`, direction, and the length of the current segment of the walk. The spiral path has a specific pattern for its segment lengths: 1 step East, 1 step South, 2 steps West, 2 steps North, 3 steps East, 3 steps South, and so on. The length of the segments increases by one after every two turns (after moving South and after moving North).

We can implement this with a loop that continues until we've found all `rows * cols` grid cells. Inside the loop, we determine the length of the next segment, then iterate that many times to take the steps. For each step, we update our coordinates, check if they are valid (inside the grid), and if so, record them. After each segment, we turn clockwise to the next direction. This method is straightforward, robust, and directly generates the coordinates in the required order.

```java
class Solution {
    public int[][] spiralMatrixIII(int rows, int cols, int rStart, int cStart) {
        int[][] result = new int[rows * cols][2];
        int i = 0;
        result[i++] = new int[]{rStart, cStart};

        int len = 0;
        int d = 0; // 0:E, 1:S, 2:W, 3:N
        int r = rStart;
        int c = cStart;

        int[] dr = {0, 1, 0, -1};
        int[] dc = {1, 0, -1, 0};

        while (i < rows * cols) {
            // When moving East or West, the length of the segment increases.
            if (d == 0 || d == 2) {
                len++;
            }
            
            // Move len steps in the current direction.
            for (int k = 0; k < len; k++) {
                r += dr[d];
                c += dc[d];
                if (r >= 0 && r < rows && c >= 0 && c < cols) {
                    result[i++] = new int[]{r, c};
                }
            }
            
            // Change to the next direction.
            d = (d + 1) % 4;
        }
        return result;
    }
}
```
### Algorithm
1. Initialize an `int[rows * cols][2]` array, `result`, to store the coordinates.
2. Add the starting coordinate `(rStart, cStart)` as the first element.
3. Initialize the current position `(r, c)` to `(rStart, cStart)`, the number of collected points `count` to 1, the current segment length `len` to 0, and the initial direction `d` to 0 (East).
4. Use a direction array `dr = {0, 1, 0, -1}` and `dc = {1, 0, -1, 0}` for East, South, West, North movements.
5. Loop while `count < rows * cols`:
    a. The spiral segment length follows the pattern 1, 1, 2, 2, 3, 3, ... for directions E, S, W, N, ... This happens to increase every time we move East or West. So, if the direction is East (`d=0`) or West (`d=2`), increment `len`.
    b. Move `len` steps in the current direction `d`. In each step:
        i. Update `r` and `c`: `r += dr[d]`, `c += dc[d]`.
        ii. Check if the new `(r, c)` is within the grid boundaries (`0 <= r < rows` and `0 <= c < cols`).
        iii. If it is, add `(r, c)` to the `result` array and increment `count`.
    c. After completing a segment, update the direction to the next one in the clockwise sequence: `d = (d + 1) % 4`.
6. Return the `result` array.

# Solutions
### Java

```java
class Solution {
public
  int[][] spiralMatrixIII(int rows, int cols, int rStart, int cStart) {
    int cnt = rows * cols;
    int[][] ans = new int[cnt][2];
    ans[0] = new int[]{rStart, cStart};
    if (cnt == 1) {
      return ans;
    }
    for (int k = 1, idx = 1;; k += 2) {
      int[][] dirs =
          new int[][]{{0, 1, k}, {1, 0, k}, {0, -1, k + 1}, {-1, 0, k + 1}};
      for (int[] dir : dirs) {
        int r = dir[0], c = dir[1], dk = dir[2];
        while (dk-- > 0) {
          rStart += r;
          cStart += c;
          if (rStart >= 0 && rStart < rows && cStart >= 0 && cStart < cols) {
            ans[idx++] = new int[]{rStart, cStart};
            if (idx == cnt) {
              return ans;
            }
          }
        }
      }
    }
  }
}

```

### JavaScript

```javascript
/** * @param {number} rows * @param {number} cols * @param {number} rStart * @param {number} cStart * @return {number[][]} */ var spiralMatrixIII =
  function (rows, cols, rStart, cStart) {
    const ans = [];
    const totalCells = rows * cols;
    const directions = [
      [0, 1],
      [1, 0],
      [0, -1],
      [-1, 0],
    ];
    let step = 0;
    let d = 0;
    let [r, c] = [rStart, cStart];
    ans.push([r, c]);
    while (ans.length < totalCells) {
      if (d === 0 || d === 2) {
        step++;
      }
      for (let i = 0; i < step; i++) {
        r += directions[d][0];
        c += directions[d][1];
        if (r >= 0 && r < rows && c >= 0 && c < cols) {
          ans.push([r, c]);
        }
      }
      d = (d + 1) % 4;
    }
    return ans;
  };

```

### CPP

```cpp
class Solution {
public:
  vector<vector<int>> spiralMatrixIII(int rows, int cols, int rStart,
                                      int cStart) {
    int cnt = rows * cols;
    vector<vector<int>> ans;
    ans.push_back({rStart, cStart});
    if (cnt == 1)
      return ans;
    for (int k = 1;; k += 2) {
      vector<vector<int>> dirs = {
          {0, 1, k}, {1, 0, k}, {0, -1, k + 1}, {-1, 0, k + 1}};
      for (auto &dir : dirs) {
        int r = dir[0], c = dir[1], dk = dir[2];
        while (dk-- > 0) {
          rStart += r;
          cStart += c;
          if (rStart >= 0 && rStart < rows && cStart >= 0 && cStart < cols) {
            ans.push_back({rStart, cStart});
            if (ans.size() == cnt)
              return ans;
          }
        }
      }
    }
  }
};

```

### Python

```python
class Solution:
    def spiralMatrixIII(self, rows: int, cols: int, rStart: int, cStart: int) -> List[List[int]]: ans = [[rStart, cStart]] if rows * cols == 1: return ans k = 1 while True: for dr, dc, dk in [[0, 1, k], [1, 0, k], [0, - 1, k + 1], [- 1, 0, k + 1]]: for _ in range(dk): rStart += dr cStart += dc if 0 <= rStart < rows and 0 <= cStart < cols: ans . append([rStart, cStart]) if len(ans) == rows * cols: return ans k += 2

```