[LeetCode] Spiral Matrix I

Problem Statement (link):

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

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

You should return [1,2,3,6,9,8,7,4,5].

Analysis:
Imagine we have a large matrix, this problem asks us to spirally traverse from outer "edges" to inside. We traverse from upper-left to upper-right, to lower-right, to lower-left, to upper-left, then we do the same traversal again on a smaller matrix, which is the "peel-off" version of the original matrix.

How should we control the start and end of each traversal? Aha, we could use recursion on the smaller matrix, repeatedly. In order to generate the smaller matrix for next traversal, we need to "peel off" the previous matrix.

A corner case to be aware of:
- If the matrix has only one row, or only one column, we should return after scanning through the row/column;

The time complexity of this algorithm is O(m*n), where m, n are the dimensions of the matrix.

Code:

class Solution {
public:
    vector<int> spiralOrder(vector<vector<int> > &matrix) {
        vector<int> out;
        if (matrix.empty()) return out;
        recur(matrix, out);
        return out;
    }

    void recur(vector<vector<int>> & matrix, vector<int> &out) {
        if (matrix.size()==0) return;

        // special case if matrix has only 1 row/col
        if (matrix.size()==1) {
            for (int i=0; i<matrix[0].size(); i++)
                out.push_back(matrix[0][i]);
            return;
        }
        if (matrix[0].size()==1) {
            for (int i=0; i<matrix.size(); i++)
                out.push_back(matrix[i][0]);
            return;
        }
       
        for (int i=0; i<matrix[0].size(); i++)
            out.push_back(matrix[0][i]);
        for (int i=1; i<matrix.size(); i++)
            out.push_back(matrix[i][matrix[0].size()-1]);
        for (int i=matrix[0].size()-2; i>=0; i--)
            out.push_back(matrix[matrix.size()-1][i]);
        for (int i=matrix.size()-2; i>=1; i--)
            out.push_back(matrix[i][0]);

        // erase the traversed values
        matrix.erase(matrix.end()-1);
        matrix.erase(matrix.begin());
        while(!matrix.empty() && matrix[0].size()==2)
            matrix.erase(matrix.begin());

        for (int i=0; i<matrix.size(); i++) {
            matrix[i].erase(matrix[i].end()-1);
            matrix[i].erase(matrix[i].begin());
        }

        recur(matrix, out);
    }
};