Super Simple and Easy to Understand Solution


  • 349
    Q

    This is a very simple and easy to understand solution. I traverse right and increment rowBegin, then traverse down and decrement colEnd, then I traverse left and decrement rowEnd, and finally I traverse up and increment colBegin.

    The only tricky part is that when I traverse left or up I have to check whether the row or col still exists to prevent duplicates. If anyone can do the same thing without that check, please let me know!

    Any comments greatly appreciated.

    public class Solution {
        public List<Integer> spiralOrder(int[][] matrix) {
            
            List<Integer> res = new ArrayList<Integer>();
            
            if (matrix.length == 0) {
                return res;
            }
            
            int rowBegin = 0;
            int rowEnd = matrix.length-1;
            int colBegin = 0;
            int colEnd = matrix[0].length - 1;
            
            while (rowBegin <= rowEnd && colBegin <= colEnd) {
                // Traverse Right
                for (int j = colBegin; j <= colEnd; j ++) {
                    res.add(matrix[rowBegin][j]);
                }
                rowBegin++;
                
                // Traverse Down
                for (int j = rowBegin; j <= rowEnd; j ++) {
                    res.add(matrix[j][colEnd]);
                }
                colEnd--;
                
                if (rowBegin <= rowEnd) {
                    // Traverse Left
                    for (int j = colEnd; j >= colBegin; j --) {
                        res.add(matrix[rowEnd][j]);
                    }
                }
                rowEnd--;
                
                if (colBegin <= colEnd) {
                    // Traver Up
                    for (int j = rowEnd; j >= rowBegin; j --) {
                        res.add(matrix[j][colBegin]);
                    }
                }
                colBegin ++;
            }
            
            return res;
        }
    }

  • 4
    Z

    This solution is excellent!! Thanks for sharing


  • 1
    Q

    glad this helps! Happy leetcoding !


  • 0
    Z

    Brilliant solution! I had the same idea but calculating depth + tail recursion.


  • 0
    P

    I used the same idea and I didn't check the condition in each while loop. Actually the maximum number can be computed. After all these loop, there are four conditions: done, one element left, one row left, one column left. and it's very straightforward to solve these conditions.

    Although I used C++, it's very easy to understand the algorithm. Hope it helps.

     class Solution{
      public: 
    vector<int> spiralOrder(vector<vector<int> > &matrix){
      //create result vector 
      vector<int> result; 
    
      //get dimension of matrix 
      int m = matrix.size(); 
      if (m==0) 
    return result; 
      int n = matrix[0].size(); 
      if (n==0)  // empty matrix 
    return result; 
      result.resize(m*n); 
    
      int i, j, k=0; //(i, j): index of matrix; k: index of vector 
      int ly, ly_max; //ly: layer; ly_max: maximum layer
      ly_max = (m>n)? (n/2):(m/2);  
      //traverse all elements 
      for(ly=0; ly<ly_max; ly++){
    //from left to right: (k,k) -> (k, n-k-2), j++
    i = ly; j=ly;  
    while(j < n-ly-1)
      result[k++] = matrix[i][j++]; 
    
    //from top to bottom: (k, n-k-1) -> (m-k-2, n-k-1), i++
    j = n-ly-1; 
    while(i < m-ly-1)
      result[k++] = matrix[i++][j]; 
    
    //from right to left: (m-k-1, n-k-1) -> (m-k-1, k+1), j--
    i = m-ly-1;  
    while(j > ly)
      result[k++] = matrix[i][j--]; 
    
    //from bottom to top: (m-k-1, k) -> (k+1, k), i--
    j=ly; 
    while(i>ly)
      result[k++] = matrix[i--][j]; 
      }
    
      // traverse left elements: one row or one column, or one element  
      if (m==n){
    if (m%2==1)
      result[k++] = matrix[ly_max][ly_max]; 
      }
      else if (m>n){
    if (n%2==1) { //column 
      i = ly_max; 
      while(i<m-ly_max)
        result[k++] = matrix[i++][ly_max]; 
    }
      }
      else{
    if (m%2==1){ //row 
      j = ly_max; 
      while(j<n-ly_max){
        cout << j << ' ' << k << ' ' << matrix[ly_max][j] <<  endl; 
        result[k++] = matrix[ly_max][j++]; 
      }
    }
      }
      return result; 
    }
    

    };


  • 0
    Q

    Thanks! happy to share :)


  • 0
    A

    I use tail recursion too and it can be easily transformed non-recursion.


  • 3
    L

    My cpp solution using same idea. state means direction and everything is just in code.

    class Solution {
    public:
        vector<int> spiralOrder(vector<vector<int> > &matrix) {
            int rows = matrix.size();
            if (rows == 0) return vector<int> ();
            int cols = matrix[0].size();
            int row = 0, col = 0, layer = 0;
            vector<int> res;
            res.push_back(matrix[0][0]);
            int state = 1;
            for (int step = 1; step < rows * cols; step++) {
                switch(state) { // based on state, check and change state, then move on
                case 1: // supposed to go right
                    if (col == cols-layer-1) { // reach right bound
                        row++;
                        state = 2;
                    }
                    else col++;
                    break;
                case 2: // supposed to go down
                    if (row == rows-layer-1) { // reach downside bound
                        col--;
                        state = 3;
                    }
                    else row++;
                    break;
                case 3: // supposed to go left
                    if (col == layer) { // reach left bound
                        row--;
                        state = 4;
                    }
                    else col--;
                    break;
                case 4: // supposed to go up
                    if (row == layer+1) { // reach upside bound
                        col++;
                        state = 1;
                        layer++;
                    }
                    else row--;
                    break;
                }
                res.push_back(matrix[row][col]);
            }
            return res;
        }
    };

  • 89
    J

    You should use an array of direction offsets if you want to be a game developer. And you don't need to check the border because rows and cols always decrease. Here is my C++ code:

    class Solution {
    public:
        vector<int> spiralOrder(vector<vector<int>> &matrix) {
            vector<int> result;
            if (matrix.empty()) return result;
            result = matrix[0];  // no need to check the first row
            int dirs[4][2] = {{1, 0}, {0, -1}, {-1, 0}, {0, 1}};  // direction offsets
            int d = 0;  // direction index
            int m = matrix.size();
            int n = matrix[0].size();
            int pos[2] = {0, n - 1};  // start from the top right corner
            int i = (m - 1) * n;  // number of the rest numbers
            while (i > 0) {
                for (int j = 1; j < m; j++) {
                    i--;
                    pos[0] += dirs[d][0]; pos[1] += dirs[d][1];
                    result.push_back(matrix[pos[0]][pos[1]]);
                }
                m--;  // decrease the size of row or column
                swap(m, n);  // switch between horizontal and vertical mode
                d = (d + 1) % 4;  // loop between direction offsets
            }
            return result;
        }
    };
    

  • 0
    L

    great idea, happy to know it, thanks.


  • 2
    L

    just return the correct list, and cut the duplicated items.

    *return order[0:len(matrix)len(matrix[0])];

    # @param matrix, a list of lists of integers
    # @return a list of integers
    def spiralOrder(self, matrix):
        if(len(matrix)==0): return matrix;
        order=[];
        
        rb,re,cb,ce=0,len(matrix)-1,0,len(matrix[0])-1;
        while(rb<=re and cb <=ce):
            for i in range(cb,ce+1):
                order.append(matrix[rb][i]);
            rb+=1;
    
            for i in range(rb,re+1):
                order.append(matrix[i][ce]);
            ce-=1;
    
            for i in range(ce,cb-1,-1):
                order.append(matrix[re][i]);
            re-=1;
            
            for i in range(re,rb-1,-1):
                order.append(matrix[i][cb]);
            cb+=1;
    
        return order[0:len(matrix)*len(matrix[0])];

  • 0
    P

    Thanks for sharing!


  • 9
    S

    mine is almost the same, but more concise

    vector<int> spiralOrder(vector<vector<int> > &matrix) {
            vector<int> ans;
            if (matrix.size() <= 0 || matrix[0].size() <= 0)
                return ans;
                
            int m = matrix.size(), n = matrix[0].size();
            int x0 = 0, x1 = m - 1; // vertical
            int y0 = 0, y1 = n - 1; // horizon
            
            while(x0 <= x1 && y0 <= y1) {    
                // travel right side
                for (int j = y0; j <= y1; ++j)
                    ans.push_back(matrix[x0][j]);
                x0++;
                
                // travel down side
                for (int i = x0; i <= x1; ++i)
                    ans.push_back(matrix[i][y1]);
                y1--;
                
                if (x0 > x1) break;
                // travel left side
                for (int j = y1; j >= y0; --j) 
                    ans.push_back(matrix[x1][j]);
                x1--;
                
                if (y0 > y1) break;
                // travel up side
                for (int i = x1; i >= x0; --i)
                    ans.push_back(matrix[i][y0]);
                y0++;
            }
            
            return ans;
        }

  • 0
    M

    like the game driven idea


  • 1
    W

    My idea is to shrink the border until reach the limit.

    class Solution:
    # @param matrix, a list of lists of integers
    # @return a list of integers
    def spiralOrder(self, matrix):
        alist = []
        while(True):
            try:
                # Top border
                alist.extend(matrix.pop(0))
                # Right border
                for item in matrix:
                    alist.append(item.pop())
                # Bottom border
                alist.extend(matrix.pop()[::-1])
                # Left border
                for item in matrix[::-1]:
                    alist.append(item.pop(0))
            # matrix.pop doesn't work if vide
            except IndexError as indexerr:
                break
    
        if [] in alist:
            alist.remove([])
        return alist

  • 3
    L

    the idea of embedding direction into the algorithm is novel.
    But acutually it sacrifies the readability of the code.
    Considering the similar complexity of the code, I prefer the original one.


  • 0
    T

    Thanks for your clear code!


  • 0
    T

    so beautiful


  • 0
    S

    Why would you need to put the rowBegin<=rowEnd condition in front of the third loop? If the condition is not met shouldn't the while loop end immediately after the increment/decrement of these pointers?


  • 0
    A

    Think about a simple case like a 1X3 matrix.


Log in to reply
 

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