# LC 59. Spiral Matrix II

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

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

Given a positive integer <code>n</code>, generate an <code>n x n</code> <code>matrix</code> filled with elements from <code>1</code> to <code>n²</code> in spiral order.

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

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

**Example 2:**

Input: n = 1
Output: [[1]]

**Constraints:**

- <code>1 <= n <= 20</code>

## Solution 1
#### Python

class Solution:
    def generateMatrix(self, n: int) -> List[List[int]]:
        left, right, up, down = 0, n - 1, 0, n - 1
        direction = 0
        res = [[0 for i in range(n)] for i in range(n)]
        cnt = 1

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

            direction = (direction + 1) % 4

        return res

#### C++

class Solution {
public:
    vector<vector<int>> generateMatrix(int n) {
        vector<vector<int>> res(n, vector<int>(n, 0));
        int left = 0, right = n - 1, up = 0, down = n - 1;
        int dir = 0;
        int cnt = 1;

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

## Solution 2 - Math
#### Python

class Solution:
    def generateMatrix(self, n: int) -> List[List[int]]:
        res = [[0] * n for _ in range(n)]
        x, y, dx, dy = 0, 0, 0, 1
        
        for i in range(1, n ** 2 + 1):
            res[x][y] = i
            if res[(x + dx) % n][(y + dy) % n] > 0:
                dx, dy = dy, -dx    # rotation matrix
            x += dx
            y += dy

        return res
    

>### Complexity
>| | Time Complexity | Space Complexity |
>| ----------- | --------------- | ---------------- |
>| Solution 1 | O($n^2$) | O($n^2$) |
>| Solution 2 | O($n^2$) | O($n^2$) |

## Note
solution 1:
[Spiral Matrix I](https://hackmd.io/heqg5HuJSfi7tx8OaEzF_Q)
solution 2:
Every time (dx, dy) will rotate 90 degrees counterclockwise.
rotation matrix =


Memories of College Linear Algebra...