Spiral Matrix

Today I came across LeetCode #54, Spiral Matrix, which an interesting one.

Problem Statement

Given an m x n matrix, return all elements of the matrix in spiral order.

Sample test case

In the given image, the input was:
Input: matrix = [[1,2,3],[4,5,6],[7,8,9]]
Output: [1,2,3,6,9,8,7,4,5]

Let’s understand the question

In the question, we are given a 2D matrix. We are supposed to traverse the matrix in such a way that a spiral is formed, first we get the top row values, then the right column, then the bottom row (from right to left), and then the left column (bottom to top), and then again the next inner top row, and so on.

Now, we need to keep in mind that each element should be accessed only once.

Proposed Solution

When we are solving questions with 2D matrices, the first approach should be trying to solve using indices. Over here, we’ll be taking a look at the indices.

So, we need the top row first, here, the row remains the same, while the column changes from startCol to endCol. We traverse through every element in the first row using a for loop, and then add each element to another vector.

Now that the top row is done, we go to the rightmost column. Here the column remains the same, while the row changes from startRow+1 to endRow. We again write a for loop for the same, access every element, and keep on adding elements to the result array.
Now here we need to take care of the initial value, startRow and endCol will get repeated if the for loop is initialized with just startRow, hence we initialize it with startRow + 1.

Get Eshita Chokhani’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

Next, we work on the bottom row, but this time in reverse, from endCol - 1 to startCol. The row remains the same (endRow), column decreases.

Then we go to the leftmost column, again in reverse — row goes from endRow - 1 to startRow + 1. This time column is constant (startCol). And yes, we need to be careful here as well, to avoid repeating already visited elements.

When Do We Stop?

So, startRow keeps increasing, and endRow keeps decreasing. At some point, startRow > endRow. That’s when we should stop. Same goes for columns, startCol < endColor else we start accessing already visited values.

This solution works fine for even dimensions, but for odd, we might miss or double count values. For example, when startRow == endRow, or startCol == endCol, the central row/column might get printed twice. So, we add conditions for that.

After Each Layer Traversal

startRow++;
endRow--;
endCol--;
startCol++;

Time complexity
The time complexity for the proposed solution is: O(m*n), when the matrix is of (m X n)

Implementation (code)

Code Snippet

Edge case
There is an edge case for a spiral matrix with an odd number of rows and columns. This is because, at some point, startRow == endRow, then both top and bottom row would be the same, so the values would get printed twice, which we don’t want.
That’s why we add if conditions before printing the bottom row and left column, and only print if startRow < endRow and startCol < endCol. Otherwise, we skip it.

Conclusion

This is one of those problems where handling the boundaries properly is the main challenge. Once you understand the movement and update the boundaries smartly after every loop, the problem becomes straightforward.

Oh and yes, Spiral Matrix II (LeetCode #59) isn’t much different. Here, we are given just a value n, and we need to generate a matrix of size n x n filled in spiral order.
We use a similar logic, just initialize a count variable and increment it with each filled cell. That’s it.
We don’t need the if conditions in this case, because we are filling the matrix from scratch, there's no chance of overlap or repeated access.