An easy to understand solution


  • 11
    D

    This solution use a most left up point and a most right bottom point to act as limiters, and traverse around directly. I think it's quite easy to understand.

    public List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> list = new LinkedList<Integer>();
        if (matrix == null) return list;
        int m = matrix.length;
        if (m == 0) return list;
        int n = matrix[0].length;
        int x0 = 0, y0 = 0; // most left up point
        int x1 = m-1, y1 = n-1; // most right bottom point
        int x = 0, y = 0;
        while(x0 < x1 && y0 < y1) {
            x = x0; // after one loop, (x, y) goes back to original position, must set them 'forward'
            y = y0;
            // traverse around
            while (y < y1) list.add(matrix[x][y++]);
            while (x < x1) list.add(matrix[x++][y]);
            while (y > y0) list.add(matrix[x][y--]);
            while (x > x0) list.add(matrix[x--][y]);
            // move limiters to center
            x0++; 
            y0++;
            x1--;
            y1--;
        }
        x = x0;
        y = y0;
        // deal with one row or col left case
        if (x0 == x1 && y0 <= y1) {
            while (y <= y1) list.add(matrix[x][y++]);
        } else if (y0 == y1 && x0 <= x1) {
            while (x <= x1) list.add(matrix[x++][y]);
        }
        return list;
    }

  • 0
    Y

    Great, haha I have nearly the same solution as yours, but yours is cleaner. There is a small typo if the last if statement, x0==x1 && y0<=y1


  • 0
    D

    Thanks! Already corrected.


  • 0
    W

    My solution is very easy to understand. I divided the traverse to two parts.

    The first part is normal order, which is from left to right and from top to bottom. The second part is reversed order, which is from right to left and from bottom to top.

    The following is accepted codes. If there is any error, feel free to comment it. Thanks.

    class Solution {
    public:
        vector<int> spiralOrder(vector<vector<int> > &matrix) {
            vector<int> result;
            if(matrix.empty() || matrix[0].empty()){return result;}
            int row_beg=0, col_beg=0, row_end=matrix.size()-1, col_end=matrix[0].size()-1;
            bool reverse=false;
            while (true){
                if(row_beg>row_end || col_beg>col_end){break;}
                if(reverse){
                    for(int i=col_end; i>col_beg; i--){
                        result.push_back(matrix[row_end][i]);
                    }
                    for(int i=row_end; i>=row_beg; i--){
                        result.push_back(matrix[i][col_beg]);
                    }
                    row_end--;
                    col_beg++;
                }else{
                    for(int i=col_beg; i<col_end; i++){
                        result.push_back(matrix[row_beg][i]);
                    }
                    for(int i=row_beg; i<=row_end; i++){
                        result.push_back(matrix[i][col_end]);
                    }
                    row_beg++;
                    col_end--;
                }
                reverse = !reverse;
            }
            return result;
        }
    };

  • 1
    C

    I'd like to share my solution as well. Hope this could be useful to you.

    class Solution {
    public:
        vector<int> spiralOrder(vector<vector<int> > &matrix)
        {
            vector<int> result;
            if (!matrix.size() || !matrix[0].size()) return result;
            int l = 0, r = matrix[0].size() - 1;
            int u = 0, d = matrix.size() - 1;
            while (l <= r && u <= d)
            {
                for (int i = l; i <= r; i++)
                    result.push_back(matrix[u][i]);
                u++;
                if (u > d) continue;
                for (int i = u; i <= d; i++)
                    result.push_back(matrix[i][r]);
                r--;
                if (l > r) continue;
                for (int i = r; i >= l; i--)
                    result.push_back(matrix[d][i]);
                d--;
                if (u > d) continue;
                for (int i = d; i >= u; i--)
                    result.push_back(matrix[i][l]);
                l++;
            }
            return result;
        }
    };

  • 4
    S

    I modified your code a little bit

    public class Solution {
        public List<Integer> spiralOrder(int[][] matrix) {
    
            List<Integer> result = new ArrayList<Integer>();
            
            if(matrix == null || matrix.length == 0 || matrix[0].length == 0) return result;
            
            int iMin = 0;
            int iMax = matrix.length - 1;
            int jMin = 0;
            int jMax = matrix[0].length - 1;
            
            int i = 0;
            int j = 0;
            
            while(iMin <= iMax && jMin <= jMax){
                while(j <= jMax) result.add(matrix[i][j++]); j--; i++; if(i > iMax) break;
                while(i <= iMax) result.add(matrix[i++][j]); i--; j--; if(j < jMin) break;
                while(j >= jMin) result.add(matrix[i][j--]); j++; i--; if(i <= iMin) break;
                while(i >= iMin + 1) result.add(matrix[i--][j]); i++; j++;
                
                iMin++;
                jMin++;
                iMax--;
                jMax--;
            }
            
            return result;
        }
    }

Log in to reply
 

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