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 rows and columns. denotes that the cell on theth row and th column was previously visited. Our current position is , facing direction , and we want to visit x total cells.
As we move through the matrix, our candidate next position is . 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

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

Space Complexity: , the information stored in
seen
and inans
.
Approach #2: LayerbyLayer [Accepted]
Intuition
The answer will be all the elements in clockwise order from the firstouter layer, followed by the elements from the secondouter layer, and so on.
Algorithm
We define the th outer layer of a matrix as all elements that have minimum distance to some border equal to . For example, the following matrix has all elements in the firstouter layer equal to 1, all elements in the secondouter layer equal to 2, and all elements in the thirdouter layer equal to 3.
[[1, 1, 1, 1, 1, 1, 1], [1, 2, 2, 2, 2, 2, 1], [1, 2, 3, 3, 3, 2, 1], [1, 2, 2, 2, 2, 2, 1], [1, 1, 1, 1, 1, 1, 1]]
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 topleft coordinates and bottomright coordinates .
Then, the top row is the set of elements for , in that order. The rest of the right side is the set of elements for , in that order. Then, if there are four sides to this layer (ie., and ), we iterate through the bottom side and left side as shown in the solutions below.
Complexity Analysis

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

Space Complexity: , the information stored in
ans
.
Analysis written by: @awice