{x}
blog image

Spiral Matrix III

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:

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

Example 2:

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

Solution Explanation: Spiral Matrix III

This problem requires generating a spiral matrix traversal sequence, starting from a given point (rStart, cStart) and considering the possibility of moving outside the grid boundaries. The solution uses a simulation approach that iteratively moves in a clockwise spiral pattern.

Approach

The core idea is to simulate the spiral traversal using a loop that increases the step size (k) with each iteration. The spiral is constructed by repeatedly moving in four directions (East, South, West, North) for k steps, then increasing k by 2 to form the next layer of the spiral.

Code Explanation (Python)

The Python solution efficiently implements this approach.

class Solution:
    def spiralMatrixIII(
        self, rows: int, cols: int, rStart: int, cStart: int
    ) -> List[List[int]]:
        ans = [[rStart, cStart]]  # Initialize with starting point
        if rows * cols == 1:  # Handle trivial case of 1x1 grid
            return ans
        k = 1  # Initialize step size
        while True:  # Iterate until all cells are visited
            for dr, dc, dk in [[0, 1, k], [1, 0, k], [0, -1, k + 1], [-1, 0, k + 1]]:
                # Iterate through East, South, West, North directions
                for _ in range(dk):  # Move dk steps in current direction
                    rStart += dr
                    cStart += dc
                    if 0 <= rStart < rows and 0 <= cStart < cols:
                        # Add valid coordinates to the result
                        ans.append([rStart, cStart])
                        if len(ans) == rows * cols:  # Check if all cells are visited
                            return ans
            k += 2  # Increment step size for the next spiral layer
  • ans = [[rStart, cStart]]: Initializes the result list with the starting coordinates.
  • if rows * cols == 1:: Handles the base case where the grid is 1x1.
  • k = 1: Starts with a step size of 1.
  • while True:: The main loop continues until all cells are visited.
  • for dr, dc, dk in [[0, 1, k], [1, 0, k], [0, -1, k + 1], [-1, 0, k + 1]]:: This loop iterates through the four directions (East, South, West, North), where dr and dc represent the row and column changes, and dk is the number of steps in that direction.
  • for _ in range(dk):: Moves dk steps in the current direction.
  • if 0 <= rStart < rows and 0 <= cStart < cols:: Checks if the current coordinates are within the grid boundaries.
  • ans.append([rStart, cStart]): Adds valid coordinates to the result list.
  • if len(ans) == rows * cols:: Checks if all cells have been visited.
  • k += 2: Increases the step size for the next spiral layer.

Time and Space Complexity

  • Time Complexity: O(rows * cols), as each cell is visited exactly once.
  • Space Complexity: O(rows * cols) in the worst case to store the result list. In practice, it's likely to be lower depending on the rows and cols and the rStart, cStart values.

The other code examples (Java, C++, Go, TypeScript, JavaScript) follow a similar logic, but with syntax specific to their respective languages. The core algorithmic approach remains consistent across all implementations.