Approach #1: Simulation [Accepted]

Intuition

Draw the path that the spiral makes. We know that the path should turn clockwise whenever it would go out of bounds or into a cell that was previously visited.

Algorithm

Let the array have $$\\text{R}$$ rows and $$\\text{C}$$ columns. $$\\text{seen[r][c]}$$ denotes that the cell on the $$\\text{r}$$ -th row and $$\\text{c}$$ -th column was previously visited. Our current position is $$\\text{(r, c)}$$ , facing direction $$\\text{di}$$ , and we want to visit $$\\text{R}$$ x $$\\text{C}$$ total cells.

As we move through the matrix, our candidate next position is $$\\text{(cr, cc)}$$ . If the candidate is in the bounds of the matrix and unseen, then it becomes our next position; otherwise, our next position is the one after performing a clockwise turn.

Complexity Analysis

\n
• \n

  Time Complexity: $$O(N)$$ , where $$N$$ is the total number of elements in the input matrix. We add every element in the matrix to our final answer.

  \n
\n
• \n

  Space Complexity: $$O(N)$$ , the information stored in seen and in ans.

  \n
\n

Approach #2: Layer-by-Layer [Accepted]

Intuition

The answer will be all the elements in clockwise order from the first-outer layer, followed by the elements from the second-outer layer, and so on.

Algorithm

We define the $$\\text{k}$$ -th outer layer of a matrix as all elements that have minimum distance to some border equal to $$\\text{k}$$ . For example, the following matrix has all elements in the first-outer layer equal to 1, all elements in the second-outer layer equal to 2, and all elements in the third-outer layer equal to 3.

[[1, 1, 1, 1, 1, 1, 1],\n [1, 2, 2, 2, 2, 2, 1],\n [1, 2, 3, 3, 3, 2, 1],\n [1, 2, 2, 2, 2, 2, 1],\n [1, 1, 1, 1, 1, 1, 1]]\n

For each outer layer, we want to iterate through its elements in clockwise order starting from the top left corner. Suppose the current outer layer has top-left coordinates $$\\text{(r1, c1)}$$ and bottom-right coordinates $$\\text{(r2, c2)}$$ .

Then, the top row is the set of elements $$\\text{(r1, c)}$$ for $$\\text{c = c1,...,c2}$$ , in that order. The rest of the right side is the set of elements $$\\text{(r, c2)}$$ for $$\\text{r = r1+1,...,r2}$$ , in that order. Then, if there are four sides to this layer (ie., $$\\text{r1 < r2}$$ and $$\\text{c1 < c2}$$ ), we iterate through the bottom side and left side as shown in the solutions below.

Complexity Analysis

\n
• \n

  Time Complexity: $$O(N)$$ , where $$N$$ is the total number of elements in the input matrix. We add every element in the matrix to our final answer.

  \n
\n
• \n

  Space Complexity: $$O(N)$$ , the information stored in ans.

  \n
\n

Analysis written by: @awice