885. Spiral Matrix III

Spiral Matrix III (LeetCode 885) is a Medium Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Array/Matrix Manipulation Patterns pattern, in the Spiral Traversal subpattern.

How to solve Spiral Matrix III

Spiral Matrix III is a Spiral Matrix Traversal problem, part of Array/Matrix Manipulation Patterns. Master spiral traversal pattern for 2D matrices. Learn to traverse matrices in spiral order for interview problems.

Work towards the solution in these steps:

1. Visualize the grid and consider how to represent your path as you move in a spiral pattern; think about how to keep track of visited cells efficiently.
2. Since the movement is in a clockwise spiral, identify the four possible directions (east, south, west, north) and how direction changes occur after a certain number of steps.
3. Notice that the number of steps you take in a given direction increases after every two direction changes; this pattern helps you know when to change direction and how far to move.

The reference solution runs in O(rows * cols) time and O(rows * cols) space.

The Spiral Matrix III solution and editorial walks through the full approach with reference code.

Problem statement

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

Topics and companies

Topics: Array, Matrix, Simulation.

Reported in interviews at Facebook.

How to practise Spiral Matrix III on Thita.ai

Starter code is provided in C, C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(rows * cols) time and O(rows * cols) space.

Open Spiral Matrix III in the code editor, or read the Spiral Matrix III editorial for a worked solution with its approach and complexity analysis.

Where Spiral Matrix III sits in the DSA pattern sheet

• Array/Matrix Manipulation Patterns pattern guide
• Spiral Traversal subpattern
• The full DSA patterns sheet

Problems related to Spiral Matrix III

Other problems that use the same Spiral Traversal and Array/Matrix Manipulation Patterns techniques:

• Spiral Matrix — Medium, same subpattern
• Spiral Matrix II — Medium, same subpattern
• Spiral Matrix IV — Medium, same subpattern
• Add Binary — Easy, same pattern
• Add to Array-Form of Integer — Easy, same pattern
• Concatenation of Array — Easy, same pattern

Spiral Matrix III FAQ