Ace Your Coding Interviews

Let's begin by tracing this out by hand and understanding what is happening.

Or if we viewed it as paths:

Let's start from the beginning. We start at the top-left (0,0) point. We walk across the first row from the first column to the last column. We are at the top-right point (0,3).

Once we reach this point, we have come to the end of the first side. Now we walk down the final column across all the rows. Once we reach the final row, we have completed traversing this side and are at the bottom-right point (3,3).

We then walk in the reverse order through the final row from the last column to the first column, reaching the bottom-left point (3,0).

To complete this first loop, we walk up the left side. However, since we have already visited (0,0), we end this loop at point (1,0).

To summarize, we walk the entire length of each side right-down-left-up for the perimeter. On the up-traversal though, we stop 1 spot back since we had already visited that point.

Now if we want to continue our traversal, we see that our problem looks identical to how we started. We need to walk the "new" perimeter and move the final index of each side inward by one.

Can you take this logic and transcribe it into code?

The logic seems straight forward. We walk an entire side until we reach a node that we have already visited. Then we turn 90° and walk the next side. We repeat this pattern until we reach the center of the matrix which means there are no unvisited nodes in our path.

This now presents three questions:

1. How do we determine if we have visited a node?
2. How will we walk the matrix in code?
3. When do we know that we've reached the center of the matrix?

If your mind immediately thought of a hash table to track the visited cells, I want to applaud you 👏👏. This is usually a good first intuition and means you understand the value of constant time O(1) inserts/lookups. However, we also know that using a hash table adds an additional linear O(n) space to our solution.

Looking back at the path of our matrix walk, we see that when we reach our starting point after walking the perimeter, we ended one index back at (1,0). If we walk each side again, we can see that this happens every time — we just end one index closer to the center.

It is the same problem repeated over and over but just shifted inward. If we solve it once, we can repeat the logic for every loop of the matrix until we reach the center.

Since we walk this repeating pattern and simply shift an index towards the center each time we complete a side, we can derive the visited nodes from the position we are at during the walk with a lower and upper bounding index. We will need an index to track the start and end for both columns and rows. This means we can do it using 4 variables which reduces our space cost to constant O(1), beating our hash table.

Now let's code out how we would walk the initial perimeter so we can gain a better intuition of how the indexes work.

Taking our initial walk around the perimeter:

1. We walk the full size of the first row (beginning to end)
2. We walk the full size of the last column (beginning to end)
3. We walk the full size of the last row (end to beginning)
4. We walk the full size - 1 of the first column (end to beginning - 1)

If we translate that to code, it would look like the following:

As the code shows, tracking indexes and making sure you aren't off by 1 is very important for this problem.

We can see that when we walk right, we start at 0 and go to the length - 1. Then when we walk left we start at length - 1 and walk backward to 0. For down it's the same, but then when we go back up, we stop one spot early.

Then if we started our perimeter walk again, we are now initially at (1,1) and would end at (1, length - 2). This would be the same for each side. We increase our lower bounds by 1 and decrease the upper bounds by 1.

Once you complete a side, you know that it will no longer be available for access, so you can bring the bounding side in by 1 index. To generalize the code we just wrote in this manner, it would become:

Our indexing is much more logically tracked.

So we know how to walk a perimeter, and it is generalized to handle when we step inward and tighten up the bounds. How do we know when we have visited every node and can stop iterating?

We continue to walk the matrix inwards until we visit all the nodes. Intuitively we know that we have finished the problem when the start and end indexes collapse in on themselves, which means the start row equals the end row, and the start column equals the end column. If the bounds are equal or move past each other, all the options have been used. We will iterate through the matrix while the end row/column is greater than or equal to the start row/column. Translated to code: while (endRow >= startRow && endColumn >= startColumn)

Now let's consider an edge case. What if there is only 1 row or column remaining? If we have a final row with the numbers [100, 200, 300], we want to make sure we iterate across correctly on the first pass start -> end, but we want to make sure that we don't iterate back across the values when we go end -> start since they have already been accounted for. So before we begin our last two for loops, we need to ensure our start/end indexes are still within the bounds since we updated the bounds after the first two loops for the rows and columns.

Alright, we're tracking visited nodes, walking the array inwards, and stopping when our indexes pass the upper and lower bounds. Let's put this all together in a working solution.