Solution by gpcode


  • 0
    G

    Preliminaries

    Consider an $$n\times n$$ matrix. The $$90^o$$ clockwise rotation is a very specific map. By inspection we observe

    • The (0,0) entry is mapped to the (0,n-1) entry,
    • The (1,0) entry is mapped to the (0,n-2) entry,
    • The (0,1) entry is mapped to the (1,n-1) entry,
    • ...
    • The (i,j) entry is mapped to the (j,n-1-i) entry.

    This is the map we need to implement.

    Approach #1 Using Another Matrix [Violating Space Complexity]

    Algorithm

    We copy all entries to another matrix, then copy all entries back
    according to the map.

    Python

    class Solution(object):
        def rotate(self, matrix):
            """
            :type matrix: List[List[int]]
            :rtype: void Do not return anything, modify matrix in-place instead.
            """
            n = len(matrix[0])
            if n == 0:
                return
            matrix_temp = [ [0 for i in xrange(n)] for i in xrange(n)]
            self.print_mat(matrix_temp)
            ## copy all entries to second matrix
            for i in xrange(n):
                for j in range(n):
                    matrix_temp[i][j] = matrix[i][j]
            for i in xrange(n):
                for j in range(n):
                    ## implement map (i,j) --> (j,n-1-i)
                    matrix[j][n-1-i] = matrix_temp[i][j]
    

    Complexity Analysis
    Recall that $$n$$ is the number of rows (or columns) so the size of input
    is actually $$n^2$$.

    • Time complexity : $$O(n^2)$$.
    • Space complexity: $$O(n^2)$$, since we are allocating another matrix.

    Approach #2 Swap Quadruple [Accepted]

    ** Intuition **
    Notice that the map give rise to a cycle of swaps of size 4:
    (i,j) --> (j,n-1-i) --> (n-1-i,n-1-j) --> (n-1-j,i) --> (i,j)

    Ergo, we can have approximately $$\frac{n^2}{4}$$ iterations, wherein each
    we swap four entries using only one temporary int.

    Algorithm

    By inspection, one can see that we need to iterate over have of the rows.
    For row $$i$$, we need to iterate over columns $$i$$ through $$n-2-i$$.
    In each iteration, we perform 4 swaps.

    Python

    class Solution(object):
        def rotate(self, matrix):
            """
            :type matrix: List[List[int]]
            :rtype: void Do not return anything, modify matrix in-place instead.
            """
            n = len(matrix[0])
            if n == 0:
                return
            for i in range(0,(n)/2 +1):
                for j in range(line,n-1-line):
                    temp = matrix[line][col]
                    matrix[line][col] = matrix[n-1-col][line]
                    matrix[n - 1 - col][line] = matrix[n - 1 - line][n - 1 - col]
                    matrix[n - 1 - line][n - 1 - col] = matrix[col][n - 1 - line]
                    matrix[col][n - 1 - line] = temp
    

    Complexity Analysis
    Recall that $$n$$ is the number of rows (or columns) so the size of input
    is actually $$n^2$$.

    • Time complexity : $$O(n^2)$$.
    • Space complexity: $$O(1)$$.

Log in to reply
 

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