Two solutions are given with comments (one is more concise with one "for")


  • 1
    D

    The first version is to use the array offset to save the offsets for each edge it walks through. For example, the first step is to walk through the top row, thus for each step, the coordinate (x,y) should be updated by adding (0,1) to move it to the right. Also another array count is used to represent how many steps it should go through each edge. count[0] is for horizontal moves and count[1] is for vertical moves.
    i is used to track which edge currently it goes through (0: top row, 1:right edge, 2:bottom raw, 3:left column), only one "for" iteration for all four edges.

    class Solution {
    public:
        vector<int> spiralOrder(vector<vector<int>>& matrix) {
            vector<int> res;
            int row = matrix.size();
            if(!row) return res;
            int col = matrix[0].size();
            if(!col) return res;
            
            int count[2] = {col, row};
            int offset[4][2] = {{0,1}, {1,0}, {0,-1},{-1,0}};
            int i=0, j, x=0, y=-1; // be careful, y should be initialized to "-1" to make it work
            while(count[0] && count[1])
            {
                for(j=0; j<count[i%2];j++)
                {
                    x +=  offset[i][0];
                    y +=  offset[i][1];
                    res.push_back(matrix[x][y]);
                }
                i = (i+1)%4; // update i before update count   
                count[i%2]--;
            }
            return res;
        }
    };
    

    // Second version: it is easy to understand but redundant. It uses 4 "for" to go through 4 edges and use four variables to check the boundary.

       vector<int> spiralOrder(vector<vector<int>>& matrix) {
            vector<int> res;
            int row = matrix.size();
            if(!row) return res;
            int col = matrix[0].size();
            if(!col) return res;
    
            int left = 0, right = col-1;
            int top = 0, bottom =row-1;
            
            int i;
            while(left<=right && top<=bottom)
            {
                for(i=left;i<=right; i++)
                {
                    res.push_back(matrix[top][i]);
                }
                top++;
                for(i=top;i<=bottom; i++)
                {
                    res.push_back(matrix[i][right]);
                }
                right--;
                if(top>bottom) break;
                for(i=right;i>=left; i--)
                {
                    res.push_back(matrix[bottom][i]);
                }
                bottom--;
                if(left>right) break;
                for(i=bottom;i>=top; i--)
                {
                    res.push_back(matrix[i][left]);
                }
                left++;
            }
            return res;
    }
    }

Log in to reply
 

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