# LC 54. Spiral Matrix

### [Problem link](https://leetcode.com/problems/spiral-matrix/)

###### tags: `leedcode` `medium` `python` `c++` `DFS` `Math`

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

**Example 1:**
<img alt="" src="https://assets.leetcode.com/uploads/2020/11/13/spiral1.jpg" style="width: 242px; height: 242px;" />

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

**Example 2:**
<img alt="" src="https://assets.leetcode.com/uploads/2020/11/13/spiral.jpg" style="width: 322px; height: 242px;" />

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

**Constraints:**

- <code>m == matrix.length</code>
- <code>n == matrix[i].length</code>
- <code>1 <= m, n <= 10</code>
- <code>-100 <= matrix[i][j] <= 100</code>

## Solution 1 - DFS
#### Python

class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        q = deque([(0,0)])
        res = [matrix[0][0]]
        matrix[0][0] = "F"
        direction = [[0,1], [1,0], [0,-1], [-1,0]]    # [right, down, left, up]
        dir_idx = 0

        while q:
            x, y = q.pop()
            for i in range(len(direction)):
                dx, dy = direction[dir_idx]
                new_x, new_y = x + dx, y + dy
                if 0 <= new_x < len(matrix) and 0 <= new_y < len(matrix[0]) and matrix[new_x][new_y] != "F":
                    q.append((new_x, new_y))
                    res.append(matrix[new_x][new_y])
                    matrix[new_x][new_y] = "F"
                    break
                else:
                    dir_idx = (dir_idx + 1) % len(direction)

        return res

## Solution 2
#### Python

class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        left, right, up, down = 0, len(matrix[0]) - 1, 0, len(matrix) - 1
        direction = 0
        res = []

        while left <= right and up <= down:
            if direction == 0:      # right
                for i in range(left, right + 1):
                    res.append(matrix[up][i])
                up += 1
            elif direction == 1:    # down
                for i in range(up, down + 1):
                    res.append(matrix[i][right])
                right -= 1
            elif direction == 2:    # left
                for i in range(right, left - 1, -1):
                    res.append(matrix[down][i])
                down -= 1
            else:                   # up
                for i in range(down, up - 1, -1):
                    res.append(matrix[i][left])
                left += 1

            direction = (direction + 1) % 4

        return res

#### C++

class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        int rows = matrix.size(), cols = matrix[0].size();
        int up = 0, down = rows - 1, left = 0, right = cols - 1;
        int dir = 0;
        vector<int> res;

        while (left <= right and up <= down) {
            if (dir == 0) {
                for (int i = left; i <= right; i++) {
                    res.push_back(matrix[up][i]);
                }
                up++;
            } else if (dir == 1) {
                for (int i = up; i <= down; i++) {
                    res.push_back(matrix[i][right]);
                }
                right--;
            } else if (dir == 2) {
                for (int i = right; i >= left; i--) {
                    res.push_back(matrix[down][i]);
                }
                down--;
            } else {
                for (int i = down; i >= up; i--) {
                    res.push_back(matrix[i][left]);
                }
                left++;
            }
            dir = (dir + 1) % 4;
        }
        return res;
    }
};

>### Complexity
>m = matrix.length
>n = matrix[i].length
>| | Time Complexity | Space Complexity |
>| ----------- | --------------- | ---------------- |
>| Solution 1 | O(mn) | O(mn) |
>| Solution 2 | O(mn) | O(mn) |

## Note
x