LeetCode 885 - Spiral Matrix III

The problem is asking us to generate the coordinates of cells in a 2D grid that we would visit if we started at a given cell (rStart, cStart) and walked in a clockwise spiral pattern.

leetcodemediumarraymatrixsimulation

LeetCode Problem 885

Difficulty: 🟡 Medium
Topics: Array, Matrix, Simulation

Solution

Problem Understanding

The problem is asking us to generate the coordinates of cells in a 2D grid that we would visit if we started at a given cell (rStart, cStart) and walked in a clockwise spiral pattern. The grid has dimensions rows x cols, and the top-left corner is (0, 0) while the bottom-right corner is (rows - 1, cols - 1). We start by facing east, move one step at a time, and follow the spiral pattern: east, south, west, north, then repeat with expanding steps.

The input parameters are rows and cols specifying the grid size, and rStart and cStart specifying the starting position. The output should be a list of all positions visited in the exact order we encounter them, including handling steps outside the grid boundaries (these should be skipped in the output).

Constraints tell us that the grid is relatively small (1 <= rows, cols <= 100), so brute-force approaches are feasible but unnecessary. Edge cases include starting at the grid boundary, having only a single row or column, and grids of size 1x1 where the spiral has minimal movement. The problem guarantees a valid starting position within the grid.

Approaches

The brute-force approach involves simulating every single step of the spiral in an unbounded coordinate plane and checking at each step whether the current cell is inside the grid. We would continue this until all cells in the grid have been visited. This works because the spiral eventually reaches all cells. However, it is slightly inefficient because it calculates many positions outside the grid that do not contribute to the result.

The optimal approach leverages the fact that the spiral moves in predictable steps that increase after every two directions. By using a direction vector and controlling the step length incrementally, we can systematically generate only the coordinates we need. The key insight is that the spiral's movement pattern is repetitive and structured, so we can iterate in a controlled loop until we have visited all rows * cols cells. This avoids unnecessary checks or additional memory overhead for visited cells since each grid cell is guaranteed to be visited exactly once.

Approach Time Complexity Space Complexity Notes
Brute Force O(max(rows, cols)^2) O(rows * cols) Simulate every spiral step, check grid boundaries
Optimal O(rows * cols) O(rows * cols) Systematic spiral generation with controlled step increments

Algorithm Walkthrough

  1. Initialize a result list to store the coordinates of cells visited within the grid. Add the starting position (rStart, cStart) to this list.
  2. Define the four possible movement directions as a sequence: east (0, 1), south (1, 0), west (0, -1), and north (-1, 0).
  3. Set up variables to track the current position (r, c) and the current step length. The step length starts at 1 and increases by 1 after completing two directions (i.e., a horizontal and a vertical move).
  4. Loop until the result list contains rows * cols coordinates. For each direction in the sequence, move step_length times in that direction, updating the current coordinates at each move.
  5. After each move, check if the current position is inside the grid boundaries. If it is, append it to the result list.
  6. After completing movement in two directions (east and south, or west and north), increment the step length by 1 to expand the spiral.
  7. Continue this process until all cells are recorded in the result list.

Why it works: The algorithm works because it mimics the exact spiral pattern required by the problem and ensures every cell in the grid is visited once. The step length increment every two directions guarantees that the spiral expands outward correctly, and checking boundaries ensures only valid grid positions are included in the result.

Python Solution

from typing import List

class Solution:
    def spiralMatrixIII(self, rows: int, cols: int, rStart: int, cStart: int) -> List[List[int]]:
        result = [[rStart, cStart]]
        directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]  # east, south, west, north
        steps = 1
        r, c = rStart, cStart

        while len(result) < rows * cols:
            for i in range(4):
                dr, dc = directions[i]
                for _ in range(steps):
                    r += dr
                    c += dc
                    if 0 <= r < rows and 0 <= c < cols:
                        result.append([r, c])
                if i % 2 == 1:
                    steps += 1  # increment step length after every vertical move
        return result

The Python solution follows the algorithm exactly. The directions array ensures consistent movement in the spiral pattern. The steps variable controls the expansion of the spiral. The inner loop moves the current position and checks if the coordinates are within the grid before adding to result. Step length is incremented after every two moves (vertical direction) to maintain the spiral expansion.

Go Solution

func spiralMatrixIII(rows int, cols int, rStart int, cStart int) [][]int {
    result := [][]int{{rStart, cStart}}
    directions := [][]int{{0,1},{1,0},{0,-1},{-1,0}} // east, south, west, north
    steps := 1
    r, c := rStart, cStart

    for len(result) < rows*cols {
        for i := 0; i < 4; i++ {
            dr, dc := directions[i][0], directions[i][1]
            for j := 0; j < steps; j++ {
                r += dr
                c += dc
                if r >= 0 && r < rows && c >= 0 && c < cols {
                    result = append(result, []int{r, c})
                }
            }
            if i % 2 == 1 {
                steps++
            }
        }
    }
    return result
}

In Go, slices are used for dynamic array construction, and the approach mirrors Python. Go requires explicit indexing for 2D slices, and bounds checking is done with >= and <. Slice appends are efficient for building the result.

Worked Examples

Example 1

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

Step-by-step:

Step Direction Position Added to Result
0 Start (0,0) Yes
1 East (0,1) Yes
2 East (0,2) Yes
3 East (0,3) Yes

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

Example 2

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

Step-by-step (partial for clarity):

Step Direction Position Added to Result
0 Start (1,4) Yes
1 East (1,5) Yes
2 South (2,5) Yes
3 West (2,4) Yes
4 West (2,3) Yes
5 North (1,3) Yes

Continues until all 30 cells are visited in spiral order.

Complexity Analysis

Measure Complexity Explanation
Time O(rows * cols) Each cell in the grid is visited exactly once
Space O(rows * cols) Storing the coordinates of all cells in the result list

Since each position is added once and the spiral expands predictably, the algorithm is linear in the number of grid cells.

Test Cases

# Provided examples
assert Solution().spiralMatrixIII(1, 4, 0, 0) == [[0,0],[0,1],[0,2],[0,3]]  # single row
assert Solution().spiralMatrixIII(5, 6, 1, 4) == [
    [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]
]

# Edge cases
assert Solution().spiralMatrixIII(1, 1, 0, 0) == [[0,0]]  # single cell
assert Solution().spiralMatrixIII(3, 3, 1, 1) == [
    [1,1],[1,2],[2,2],[2,1],[2,0],[1,0],[0,0],[