Easy understand C++ O(1) Space 0ms


  • 0
    M

    Just do circle by circle from outside to inside

    class Solution {
    public:
        vector<int> spiralOrder(vector<vector<int>>& ma) {
            vector<int> ans;
            int n, m;
            n = ma.size();
            if(n == 0) return ans;
            m = ma[0].size();
            int i = -1, j = -1;
            int cnt1 = n, cnt2 = m;
            while(cnt1 > 1 && cnt2 > 1){
                i++; j++;
                for(int k = 0; k < cnt2-1; k++) ans.push_back(ma[i][j++]);
                for(int k = 0; k < cnt1-1; k++) ans.push_back(ma[i++][j]);
                for(int k = 0; k < cnt2-1; k++) ans.push_back(ma[i][j--]);
                for(int k = 0; k < cnt1-1; k++) ans.push_back(ma[i--][j]);
                cnt1 -= 2; cnt2 -= 2;
            }
            i++; j++;
            if(cnt1 == 1){
                for(int k = 0; k < cnt2; k++) ans.push_back(ma[i][j++]);
            }
            else if(cnt2 == 1){
                for(int k = 0; k < cnt1; k++) ans.push_back(ma[i++][j]);
            }
            return ans;
        }
    };
    

  • 0
    A

    0 ms results and any perf results on this site are "jut an sign that nothing hugely wrong" is done. Solving perf comparison in cloud environment is an interesting task by itself. I personally write my own perf tests and compare with solutions posted by other people. My solution submitted for this task was reported as 3ms. But when I take your code and put it into my perf test below I have 25 sec for your runtime and 7 for mine. My solution is included below too.

    int main()
    {
        Solution s;
        int antiOptimizer = 0;
    
        auto input = vector<vector<int>>{ vector<int>{1, 2, 3 }, vector<int>{4, 5, 6 }, vector<int>{7, 8, 9 } };
        
        for (int i = 0; i < 50000000; ++i)
        {
            auto r1 = s.spiralOrder(input);
            antiOptimizer += r1.size();
        }
    
        return antiOptimizer;
    }
    
    class Solution
    {
    public:
        vector<int> spiralOrder(vector<vector<int>>& matrix)
        {
            size_t rowsCount = matrix.size();
            if (rowsCount == 0)
                return vector<int>();
    
            size_t colsCount = matrix[0].size();
            if (colsCount == 0)
                return vector<int>();
    
            vector<int> result;
            result.reserve(rowsCount * colsCount);
    
            size_t r = 0;
            size_t c = numeric_limits<size_t>::max(); // 0 when 1 is added
            size_t hSteps = colsCount;
            size_t vSteps = rowsCount - 1;
            size_t steps = hSteps;
            size_t hStep = 1;
            size_t vStep = 0;
    
            while (steps > 0)
            {
                while (steps-- > 0)
                {
                    r += vStep;
                    c += hStep;
                    result.push_back(matrix[r][c]);
                }
    
                // Right turn
                if (hStep == 1)
                {
                    hStep = 0;
                    vStep = 1;
                    --hSteps;
                    steps = vSteps;
                }
                else if (vStep == 1)
                {
                    hStep = -1;
                    vStep = 0;
                    --vSteps;
                    steps = hSteps;
                }
                else if (hStep == -1)
                {
                    hStep = 0;
                    vStep = -1;
                    --hSteps;
                    steps = vSteps;
                }
                else if (vStep == -1)
                {
                    hStep = 1;
                    vStep = 0;
                    --vSteps;
                    steps = hSteps;
                }
            }
    
            return result;
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.