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 <= 1000 <= rStart < rows0 <= cStart < colsIn #885 Spiral Matrix III, you are given a grid size and a starting position. The goal is to output coordinates of cells visited while walking in a spiral pattern (east → south → west → north) until all grid cells are covered. The key challenge is that the spiral may temporarily move outside the grid boundaries, but only valid coordinates should be recorded.
A common approach is to simulate the spiral movement. Maintain a direction list and gradually increase the number of steps taken. After every two direction changes, increase the step length (e.g., 1 step east, 1 south, 2 west, 2 north, 3 east...). During movement, check whether the current coordinate is inside the grid; if so, add it to the result list.
This simulation continues until rows * cols valid coordinates are collected. The approach ensures each cell is added exactly once while following the spiral pattern. The algorithm runs in O(R × C) time since every grid cell is recorded once, with O(1) auxiliary space excluding the output.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Spiral Simulation with Expanding Steps | O(R × C) | O(1) auxiliary (O(R × C) for output) |
take U forward
To simulate walking in a spiral, maintain a direction vector and a step count for each segment. Initially face east, and keep track of direction changes in the order of east, south, west, north. After two direction changes, increase the step count which determines how far to walk in the current direction before turning.
Time Complexity: O(rows * cols), since each cell is visited once,
Space Complexity: O(rows * cols), for the result storage.
1#include <stdio.h>
2#include <stdlib.h>
3
4int** spiralMatrixIII(int rows, int cols, int rStart, int cStart, int* returnSize, int** returnColumnSizes) {
5 *returnSize = rows * cols;
6 *returnColumnSizes = (int*)malloc(sizeof(int) * (*returnSize));
7 for (int i = 0; i < *returnSize; ++i) (*returnColumnSizes)[i] = 2;
8
9 int** result = (int**)malloc(sizeof(int*) * (*returnSize));
10 int directions[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}; // right, down, left, up
11 int totalSteps = 0, steps = 1;
12 int dir = 0;
13 result[totalSteps++] = (int*)malloc(sizeof(int) * 2);
14 result[0][0] = rStart; result[0][1] = cStart;
15 int r = rStart, c = cStart;
16
17 while (totalSteps < (*returnSize)) {
18 for (int i = 0; i < steps; ++i) {
19 r += directions[dir][0];
20 c += directions[dir][1];
21 if (0 <= r && r < rows && 0 <= c && c < cols) {
22 result[totalSteps] = (int*)malloc(sizeof(int) * 2);
23 result[totalSteps][0] = r;
24 result[totalSteps][1] = c;
25 totalSteps++;
26 }
27 }
28 if (dir == 1 || dir == 3) steps++;
29 dir = (dir + 1) % 4;
30 }
31 return result;
32}This solution initializes variables for direction and position, and iterates until all grid elements are visited. For each direction, it moves step-by-step and checks boundary conditions to ensure valid indices.
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, spiral traversal and grid simulation problems are common in technical interviews, including FAANG-style interviews. They test understanding of matrix traversal, boundary handling, and simulation logic.
The problem mainly relies on simple variables and a list to store coordinates. A direction array and step counter are typically used to control movement in the spiral pattern efficiently.
The optimal approach is to simulate spiral movement starting from the given cell. By moving in four directions and increasing step lengths after every two turns, you can generate the correct spiral order while collecting valid grid coordinates.
The spiral grows outward as you move away from the starting cell. Increasing the step size after every two directions ensures the path expands evenly and forms the correct spiral pattern.