# Solution by gpcode

• #### 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)$$.

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