Seven Short Solutions (1 to 7 lines)


  • 107

    While these solutions are Python, I think they're understandable/interesting for non-Python coders as well. But before I begin: No mathematician would call a matrix matrix, so I'll use the usual A. Also, btw, the 40 ms reached by two of the solutions is I think the fastest achieved by Python solutions so far.


    Most Pythonic - [::-1] and zip - 44 ms

    The most pythonic solution is a simple one-liner using [::-1] to flip the matrix upside down and then zip to transpose it. It assigns the result back into A, so it's "in-place" in a sense and the OJ accepts it as such, though some people might not.

    class Solution:
        def rotate(self, A):
            A[:] = zip(*A[::-1])
    

    Most Direct - 52 ms

    A 100% in-place solution. It even reads and writes each matrix element only once and doesn't even use an extra temporary variable to hold them. It walks over the "top-left quadrant" of the matrix and directly rotates each element with the three corresponding elements in the other three quadrants. Note that I'm moving the four elements in parallel and that [~i] is way nicer than [n-1-i].

    class Solution:
        def rotate(self, A):
            n = len(A)
            for i in range(n/2):
                for j in range(n-n/2):
                    A[i][j], A[~j][i], A[~i][~j], A[j][~i] = \
                             A[~j][i], A[~i][~j], A[j][~i], A[i][j]
    

    Clean Most Pythonic - 56 ms

    While the OJ accepts the above solution, the the result rows are actually tuples, not lists, so it's a bit dirty. To fix this, we can just apply list to every row:

    class Solution:
        def rotate(self, A):
            A[:] = map(list, zip(*A[::-1]))
    

    List Comprehension - 60 ms

    If you don't like zip, you can use a nested list comprehension instead:

    class Solution:
        def rotate(self, A):
            A[:] = [[row[i] for row in A[::-1]] for i in range(len(A))]
    

    Almost as Direct - 40 ms

    If you don't like the little repetitive code of the above "Most Direct" solution, we can instead do each four-cycle of elements by using three swaps of just two elements.

    class Solution:
        def rotate(self, A):
            n = len(A)
            for i in range(n/2):
                for j in range(n-n/2):
                    for _ in '123':
                        A[i][j], A[~j][i], i, j = A[~j][i], A[i][j], ~j, ~i
                    i = ~j
    

    Flip Flip - 40 ms

    Basically the same as the first solution, but using reverse instead of [::-1] and transposing the matrix with loops instead of zip. It's 100% in-place, just instead of only moving elements around, it also moves the rows around.

    class Solution:
        def rotate(self, A):
            A.reverse()
            for i in range(len(A)):
                for j in range(i):
                    A[i][j], A[j][i] = A[j][i], A[i][j]
    

    Flip Flip, all by myself - 48 ms

    Similar again, but I first transpose and then flip left-right instead of upside-down, and do it all by myself in loops. This one is 100% in-place again in the sense of just moving the elements.

    class Solution:
        def rotate(self, A):
            n = len(A)
            for i in range(n):
                for j in range(i):
                    A[i][j], A[j][i] = A[j][i], A[i][j]
            for row in A:
                for j in range(n/2):
                    row[j], row[~j] = row[~j], row[j]

  • 0
    C

    awesome explanation! So pythonic!!!


  • 1
    C

    My Copy & Paste solution

    class Solution:
        # @param {integer[][]} matrix
        # @return {void} Do not return anything, modify matrix in-place instead.
        def rotate(self, matrix):
            dim = len(matrix)
            copy = [x[:] for x in matrix]
            for i in range(dim):
            	for j in range(dim):
            		matrix[i][j] = copy[~j][i]
    

    Could you explain why [~i] and [n-1-i] are equivalent?
    Thanks!


  • 2

    Due to how numbers are represented, ~i has the value -i-1. So 0, 1, 2, ... become -1, -2, -3, ... And in Python you can use negative indexes to index from the back, with index -1 referring to the last element.


  • -1
    J

    Is ~i the same as -i?


  • 0

    @jing16 No, never, so any test would have shown you. (Well, at least for integers... I guess you could define a type where it's the same).


  • 0
    L

    I am not sure. In second solution, you made anti-clockwise change, I think


  • 0
    R

    awesome !! Thanks for sharing .


  • 0
    F

    Awesome! Most Direct - 52 ms is totally a witchcraft!


  • 0
    Y

    said in Seven Short Solutions (1 to 7 lines):

    Flip Flip - 40 ms
    Basically the same as the first solution, but using reverse instead of [::-1] and transposing the matrix with loops instead of zip. It's 100% in-place, just instead of only moving elements around, it also moves the rows around.
    class Solution:
    def rotate(self, A):
    A.reverse()
    for i in range(len(A)):
    for j in range(i):
    A[i][j], A[j][i] = A[j][i], A[i][j]

    This flip filp fails for this test:
    A = [[1,2,3,6,7],[4,5,6,7,8],[5,6,7,8,9]]
    After the run,
    A = [[5, 4, 1, 8, 9], [6, 5, 2, 7, 8], [7, 6, 3, 6, 7]]
    Expected:
    A = [(5, 4, 1), (6, 5, 2), (7, 6, 3), (8, 7, 6), (9, 8, 7)]


  • 0

    @ysz I'm shown Expected answer [[5,4,1,6,7],[6,5,2,7,8],[7,6,3,8,9]]. No idea what you did. Anyway, doesn't matter, as your input is invalid (it's not a square matrix).


  • 1
    T

    why do you use A[:] = zip(*A[::-1]) ? I tried A = zip(*A[::-1]), which doesn't work.

    Do you know why this happened?


  • 0
    I

    @TiramisuV said in Seven Short Solutions (1 to 7 lines):

    why do you use A[:] = zip(*A[::-1]) ? I tried A = zip(*A[::-1]), which doesn't work.

    Do you know why this happened?

    wish someone could help us answer this one.


  • 1

    @TiramisuV said in Seven Short Solutions (1 to 7 lines):

    why do you use A[:] = zip(*A[::-1]) ? I tried A = zip(*A[::-1]), which doesn't work.

    Because I need to modify the given list object referenced by the variable A. If you do A = ..., then you're instead making the variable A reference another list object, leaving the given one unchanged.


  • 1
    T

    @StefanPochmann
    Thanks for your reply. :)


  • 0
    B

    cool.thank you.


  • 0
    L

    could anyone explain to me why in the second loop is range(n-n/2) and it does work?


  • 0
    F

    @StefanPochmann
    for integer in python, is ~i == -i - 1 always correct? is it defined by python standard?


  • 1

    @FindRX Why ask me when you can just check the documentation?


  • 0
    A
        def rotate(self, matrix):
            """
            :type matrix: List[List[int]]
            :rtype: void Do not return anything, modify matrix in-place instead.
            """
            matrix[:] = zip(*matrix[::-1])
            return matrix~~~~
    
    why it gives this error:
    
    Do not return anything, modify matrix in-place instead.

Log in to reply
 

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