# Spiral Matrix
[leetcode網址](https://leetcode.com/problems/spiral-matrix/description/)
## Idea
分成四個case，keep四個方向: `top`, `down`, `right`, `left`，然後需要兩個位移動的index: `i`走x軸，`j`走y軸
1. 往右走
- 要bound住右邊
- 走完後j=right(要往下走的column), i++(到下一層), right--(右邊bound減一)
- code

        while(j<right){
            results.push_back(matrix[i][j]);
            j++;
        }       
        j=right-1;
        right--;
        i++;

2. 往下走
- 要bound住下界
- 走完後i=down(要往左走的row), j--(column往回走), down--(下界bound減一)
- code

        while(i<down){
            results.push_back(matrix[i][j]);
            i++;
        }
        i=down-1;
        down--;
        j--;

3. 往左走
- 要bound住左邊
- 走完後j=left(要往上走的column), i--(到上一層), left++(左邊bound加一)
- code

        while(j>=left){
            results.push_back(matrix[i][j]);
            j--;
        }
        j=left;
        left++;
        i--;

4. 往上走
- 要bound住上邊
- 走完後i=top(要往又走的row), j++(column往右走), top++(上邊bound加一)
- code

        while(i>top){                
            results.push_back(matrix[i][j]);
            i--;
        }                                  
        top++;
        j++;
        i=top;

## Solution
:timer_clock: Time Complexity: O (m × n)
✶⋆.˚ Space Complexity: O(1) additional space.

vector<int> spiralOrder(vector<vector<int>>& matrix) {

    int m=matrix.size(), n=matrix[0].size();
    int top=0, down=m, left=0, right=n;
    int dir=0, i=top, j=0;
    vector<int>results;
    while(results.size()<m*n){
        dir%=4;
        switch(dir){
            case 0:
                while(j<right){
                    results.push_back(matrix[i][j]);
                    j++;
                }       
                j=right-1;
                right--;
                i++;
                break;
            case 1:
                while(i<down){
                    results.push_back(matrix[i][j]);
                    i++;
                }
                i=down-1;
                down--;
                j--;
                break;
            case 2:
                while(j>=left){
                    results.push_back(matrix[i][j]);
                    j--;
                }
                j=left;
                left++;
                i--;
                break;
            default: 
                while(i>top){                
                    results.push_back(matrix[i][j]);
                    i--;
                }                                  
                top++;
                j++;
                i=top;
                break;
        }
        dir++;
    }
    return results;
}