1-liner in Python + Ruby


  • 61

    Take the first row plus the spiral order of the rotated remaining matrix. Inefficient for large matrices, but here I got it accepted in 40 ms, one of the fastest Python submissions.

    Python:

    def spiralOrder(self, matrix):
        return matrix and list(matrix.pop(0)) + self.spiralOrder(zip(*matrix)[::-1])
    

    Ruby:

    def spiral_order(matrix)
      (row = matrix.shift) ? row + spiral_order(matrix.transpose.reverse) : []
    end
    

    or

    def spiral_order(matrix)
      matrix[0] ? matrix.shift + spiral_order(matrix.transpose.reverse) : []
    end
    

    Visualization

    Here's how the matrix changes by always extracting the first row and rotating the remaining matrix counter-clockwise:

        |1 2 3|      |6 9|      |8 7|      |4|  =>  |5|  =>  ||
        |4 5 6|  =>  |5 8|  =>  |5 4|  =>  |5|
        |7 8 9|      |4 7|
    

    Now look at the first rows we extracted:

        |1 2 3|      |6 9|      |8 7|      |4|      |5|
    

    Those concatenated are the desired result.

    Another visualization

      spiral_order([[1, 2, 3],
                    [4, 5, 6],
                    [7, 8, 9]])
    
    = [1, 2, 3] + spiral_order([[6, 9],
                                [5, 8],
                                [4, 7]])
    
    = [1, 2, 3] + [6, 9] + spiral_order([[8, 7],
                                         [5, 4]])
    
    = [1, 2, 3] + [6, 9] + [8, 7] + spiral_order([[4],
                                                  [5]])
    
    = [1, 2, 3] + [6, 9] + [8, 7] + [4] + spiral_order([[5]])
    
    = [1, 2, 3] + [6, 9] + [8, 7] + [4] + [5] + spiral_order([])
    
    = [1, 2, 3] + [6, 9] + [8, 7] + [4] + [5] + []
    
    = [1, 2, 3, 6, 9, 8, 7, 4, 5]
    

  • 0
    O

    awesome !!! but should the list() function be applied on later term (outside of zip)?


  • 2

    You mean list(zip(...))? No, that makes no sense, as zip already returns a list (we have Python 2 here). I see you do that in your solution, and you don't need it. The reason I need it is because I use + to concatenate the parts, and my base case matrix is the empty list but matrix.pop(0) is usually a tuple (since zip creates a list of tuples). And "tuple+list" is not allowed, so I need to convert each tuple to a list. In your solution you can simply work with tuples because you use extend, and lists don't mind being extended by tuples.

    Btw, in case you're wondering: It's not a coincidence that I posted mine so soon after yours, I had seen yours before posting mine. I had written mine about a month ago, though. Don't know why I didn't post it right away, maybe I wanted to post it together with my faster solution(s), which aren't polished yet...


  • 0
    O

    I see. Nice to learn this.


  • 0
    J

    Marvelous! I even don't realize that we could use zip like this! Brava!


  • 0
    B

    Really elegant solution! Thanks for sharing.


  • 0
    R

    oh my god!!!!!!


  • 0
    E

    Really clever use of a rotated matrix. Any idea how large the memory footprint is? Seems like you'll be making a number of copies of the matrix (although it will be decremented by a row/column repeatedly).


  • -1
    S

    run-time error, but it succeed in visual studio, can anyone help me?

        vector<int> spiralOrder(vector<vector<int>>& matrix) {
        vector<int> res;
        if(matrix.empty()) return res;
        int m = matrix.size();
        int n = matrix[0].size();
        
        int row=0,col=0;
        int dir=0,left=0,right=n-1,bottom=0,up=m-1;
        for(int i=0;i<m*n;++i)
        {
            res.push_back(matrix[row][col]);
            switch(dir)
            {
                case 0://right
                    if(col == right)
                    {
                        dir++;bottom++;row++;
                    }
                    else
                        col++;
                    break;
                case 1:
                    if(row == up)
                    {
                        dir++;right--;col--;
                    }
                    else
                        row++;
                    break;
                case 2:
                    if(col == left)
                    {
                        dir++;up--;row--;
                    }
                    else
                        col--;
                    break;
                case 3:
                    if(row == bottom)
                    {
                        dir=0;left++;col++;
                    }
                    else
                        row--;
                    break;
            }
        }
        return res;
    }

  • 4
    L

    Sir, I think you can publish a book with a title like "Think in Python" or "Pythonic Coding".


  • 0
    A

    Elegant solution! But much slower than others. Is it rebuilding a list to pass matrix for recursion, or zip, or reverse matrix slowing down?


  • 0
    W

    @oscartsai said in 1-liner in Python:

    applied on later term (outside of zip)?

    in python3.6, it should be add list() on the last term。
    *return matrix and list(matrix.pop(0)) + spiralOrder(list(zip(matrix))[::-1])


  • 0

    @algowl said in 1-liner in Python:

    much slower than others

    What do you mean?


  • 0
    A

    @StefanPochmann said in 1-liner in Python:

    @algowl said in 1-liner in Python:

    much slower than others

    What do you mean?

    Your runtime beats 1.60 % of python submissions.


  • 0

    @algowl That's not true. I just submitted it five times and it beat 9%, 18%, 69%, 69% and 51%. And earlier today, right before I asked you, I had submitted it three times and it beat 51%, 51% and 67%. How often did you submit it? What were the individual results?


  • 0
    W

    @StefanPochmann First, thanks for your solution.It helps me a lot. But, for this question, it justs the difference between py2 and py3. I test in my local environment.
    Just like this:
    A = [[1, 2], [3,,4]]
    zip(*A)[::-1]
    In py2, it can pass.
    But in py3.6, it gives the error likes "TypeError: 'zip' object is not subscriptable".
    So, in leetcode, it supports the py2 and py3, it can be passed.
    That all.Thanks.


  • 0
    A

    @StefanPochmann You are right. It does have a wide distribution, or the variance is too large. Sorry about the false alarm.


  • 1
    W

    This is such an elegant solution. Also learnt the star expression. Thanks!


  • 0
    H
    This post is deleted!

  • 1
    T

    @woqishi
    The problem with Python 3 is that the zip returns an iterator rather than a list. You can fix this by converting via a list comprehension:

    def spiralOrder(self, matrix):
        return matrix and matrix.pop(0) + self.spiralOrder([list(x) for x in zip(*matrix)][::-1])
    

Log in to reply
 

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