Spiral Matrix Walmart Python Interview Question

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

In case you don’t think about spirals that often (unless you're pondering galaxies or those satisfying snail shells), here’s what we mean: start at the top-left corner and move right across the first row, then down the last column, left along the bottom row, and finally back up the first column. Keep spiraling inward until you’ve collected all the elements.

It’s like peeling layers off an onion… but way less tear-inducing!

Example #1

Input: matrix = [[1, 2, 3],[4, 5, 6],[7, 8, 9]]

Output: [1, 2, 3, 6, 9, 8, 7, 4, 5]

![Spiral Matrix Example 1 DataLemur]

Example #2

Input: matrix = [[1, 2, 3],[8, 9, 4],[7, 6, 5]]

Output: [1, 2, 3, 4, 5, 6, 7, 8, 9]

Approach #1: Using Rotation to Extract Elements

This approach involves rotating the input matrix so that the numbers we need always appear in the first row. Let's work through an example to understand this better:

The first three numbers () are in the first row of the matrix. We can extract them easily.

Once we extract the first row, the remaining matrix looks like this:

Now the main question is: how do we get the rest of the numbers? Let's focus on getting the next two numbers (). Extracting them isn’t as straightforward as the first row, but what if we rotate the matrix counterclockwise? After rotating, it looks like this:

Now, the next two numbers () are in the first row! We can extract them similarly to before. After removing the first row, the remaining matrix is:

Do you notice the pattern? We are rotating the matrix counterclockwise so that the next numbers we need to extract are always in the first row. Each time we process a row, we remove it and rotate the remaining matrix.

If you haven't solved the Clockwise Matrix Rotation problem, you should do that first. In that problem, we rotate the matrix clockwise, but here we are rotating counterclockwise. You can either come up with a way to rotate the matrix counterclockwise or simply rotate the matrix clockwise three times to simulate a counterclockwise rotation.

Here is the full code:

Approach #2: Using Boundaries to Traverse

This approach uses boundaries—top, bottom, left, and right—to traverse the matrix in a spiral order. Here's what each boundary represents:

1. Top: The uppermost unprocessed row.
2. Bottom: The lowermost unprocessed row.
3. Left: The leftmost unprocessed column.
4. Right: The rightmost unprocessed column.

Now, let's modify the previous approach:

1. Instead of rotating the matrix, we follow the spiral path using the boundaries (explained below).
2. Instead of reducing the matrix size by removing rows or columns, we shrink the boundaries.

Process:

1. Traverse from the left boundary to the right boundary along the top row and append the elements to the result.
2. Shrink the top boundary (i.e., increment it) because we've processed that row.
3. Traverse from the top boundary to the bottom boundary along the right column and append the elements to the result.
4. Shrink the right boundary (i.e., decrement it) because we've processed that column.
5. Traverse from the right boundary to the left boundary along the bottom row and append the elements to the result.
6. Shrink the bottom boundary (i.e., decrement it) because we've processed that row.
7. Traverse from the bottom boundary to the top boundary along the left column and append the elements to the result.
8. Shrink the left boundary (i.e., increment it) because we've processed that column.

Repeat this process until all elements have been added to the result.

Here’s the full code: