My C++ solution 0ms (scan four edges iteratively)


  • 0
    D

    Just iteratively go through each edge, four variables, top/bottome, left/right are used to identify boundary.

    class Solution {
    public:
        vector<int> spiralOrder(vector<vector<int>>& matrix) {
            int top =0, bottom, left=-1, right, i, j, k=0;
            if((bottom=matrix.size())==0 || (right=matrix[0].size())==0) return vector<int>();
            int total = bottom-- * right--;
            vector<int> res(total, 0); 
            while(k < total)
            {
                for(j=  ++left;    j<=right;++j) res[k++] = matrix[top][j];
                if(k>=total) break;
                for(i= ++top;  i<=bottom;++i) res[k++] = matrix[i][right];
                if(k>=total) break;
                for(j= --right; j>=left    && k<total;--j)   res[k++] = matrix[bottom][j];
                if(k>=total) break;
                for(i= --bottom; i>=top    && k<total; --i)  res[k++] = matrix[i][left];
            }
            return res;
        }
    };
    

    If you don't like those "break", you can do the following

    class Solution {
    public:
        vector<int> spiralOrder(vector<vector<int>>& matrix) {
            int top =0, bottom, left=-1, right, i, j, k=0;
            if((bottom=matrix.size())==0 || (right=matrix[0].size())==0) return vector<int>();
            int total = bottom-- * right--;
            vector<int> res(total, 0); 
            while(k < total)
            {
                for(j=  ++left;    j<=right;++j) res[k++] = matrix[top][j];
                for(i= k<total? ++top:INT_MAX;  i<=bottom;++i) res[k++] = matrix[i][right];
                for(j= k<total?--right:INT_MIN; j>=left;--j)   res[k++] = matrix[bottom][j];
                for(i= k<total?--bottom:INT_MIN; i>=top; --i)  res[k++] = matrix[i][left];
            }
            return res;
        }
    };
    

    The last version is learned from stellari's post https://leetcode.com/discuss/38974/a-concise-c-implementation-based-on-directions. Basically, you can replace four "for" loops with one and to do that, we need to define two offset arrays to describe how to move x,y coordinates along four edges, and a steps array to define how many steps we should go along horizontal and vertical edges. My version is as below

    class Solution {
    public:
        vector<int> spiralOrder(vector<vector<int>>& matrix) {
            int offset_x[4] = {0,1,0,-1}, offset_y[4] = {1,0,-1,0}, row= matrix.size(), col = row>0?matrix[0].size():0, x=0, y=-1, steps[2]={col,row-1}, curDir = 0, i, k=-1;
            vector<int> res(row*col, 0);
            while(steps[curDir%2])
            {
                for(i=0;i<steps[curDir%2]; ++i) res[++k] = matrix[x+=offset_x[curDir]][y+=offset_y[curDir]];
                --steps[curDir%2];
                curDir = (curDir+1)%4;
            }
            return res;
        
        }
    };

Log in to reply
 

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