## Problem

We are given an image in the form of an n-by-n matrix and we are supposed to rotate it by 90 degrees.

```
Example:
input:
1 2 3
4 5 6
7 8 9
output:
7 4 1
8 5 2
9 6 3
```

## Solution

At first rotating the whole matrix might sound like a complicated task. But it is not! It becomes really trivial if we break the problem down. We will break the matrix rotation down into layers rotation and then rotate layer-by-layer. Now, rotating layer-by-layer can be further broken down into rotating 4 numbers of the layer at a time.

```
void rotate_4(long& a, long& b, long& c, long& d) {
// helper function
// [a, b, c, d] => [d, a, b, c]
long temp = b;
b = a;
a = c;
c = temp;
temp = d;
d = a;
a = temp;
}
void rotate_matrix(vector<vector<long>>& m) {
// nxn matrix
int n = m.size();
// l = number of layers
int l = (n + 1) / 2;
for (int i = 0; i < l; ++i) {
for (int j = i; j < n - i - 1; ++j) {
cout << j << endl;
// If the following line does not make sense, just consider a small example
rotate_4(m[i][j], m[j][n - i - 1], m[n - i - 1][n - j - 1], m[n - j - 1][i]);
}
}
}
```

References: Cracking the Coding Interview - Gayle Laakmann McDowell

Feel free to comment out a solution in your favorite programming language!

Have a marvelous day 😄

## Discussion

This is an interesting (and practical) problem.

I have trouble following the solution, though.

Here's the pattern I noticed:

1) Row #1 becomes Column #3

2) Row #2 becomes Column #2

3) Row #3 becomes Column #1

Basically, if the matrix is

`nxn`

, Row #`i`

becomes Column #`n-i+1`

.But we can make things easier for ourselves by switching up our perspective:

Algorithm:For

`col = 0`

through`n - 1`

:Iterate through the rows in reverse:

`row = n - 1 through 0`

and fill the new matrix with`original[row][col]`

Yea, your solution will work as well. It's just that it will take additional

O(nspace as we are creating a new matrix. The pattern that you mentioned is indeed what the algorithm mentioned by me does. But, since it tries to do in-place, we rotate one number of row/column at a time.^{2})