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