# Spiral Matrix I

## Problem

Given a matrix of *m* x *n* elements (*m* rows, *n* columns), return all elements of the matrix in spiral order.

{% hint style="info" %}
For example: 

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

{% endhint %}

### Thought Process:

* *How do we know when we reach the end of one of the inner arrays inside the matrix?*

  * By setting boundaries for top, bottom, left, and right. We update the boundaries when a row or column is complete.

* *How do we know when to go down, left, right, or up?*

  * By having a variable representing the direction to go in. d = 0 (right), d = 1 (down), d = 2 (left), d = 3 (up)

* *How do we know when we reach the end of the spiral?*
  * We have an outer while loop checking the boundaries. When the top boundary has passed the bottom boundary and when the left boundary has passed the right boundary, the loop will break.

## Solution

```
class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        if len(matrix) == 0:
            return []
        d = 0
        top,bottom = 0, len(matrix)-1
        left,right = 0, len(matrix[0])-1
        soln = []
        
        while top <= bottom and left <= right:
            if d == 0:
                for j in range(left, right+1):
                    soln.append(matrix[top][j])
                top+=1
                d+=1
            elif d == 1:
                for i in range(top, bottom+1):
                    soln.append(matrix[i][right])
                right-=1
                d+=1
            elif d == 2:
                for j in range(right, left-1, -1):
                    soln.append(matrix[bottom][j])
                bottom-=1
                d+=1
            elif d == 3:
                for i in range(bottom, top-1,-1):
                    soln.append(matrix[i][left])
                left+=1
                d = 0
        return soln
                    
                
        
```

## Key Facts

* The direction variable and boundary variables is what really helps solve this problem and are the main driving force for this solution.&#x20;
* We are essentially "shaving off" each row and column.

## Time Complexity

**Time**: O(n) because we are going through every number in the matrix

**Space**: O(n) for the single array we are storing our solution in