# How to Rotate a Matrix (Clockwise and Anti-clockwise) in place?

in #codeonsteem27 days ago

Given a matrix with dimension NxN, rotate the matrix in place the 90 degrees clockwise and anti-clockwise.

For example, original Matrix 3x3:

``````vector<vector<int>> matrix({
{1, 2, 3},
{4, 5, 6},
{7, 8, 9}
});
``````

Rotating it 90 degree clockwise would make it:

``````vector<vector<int>> matrix({
{7, 4, 1},
{8, 5, 2},
{9, 6, 3}
});
``````

To solve this problem, the tricks is to use two-step process: First Transpose the matrix (which mirrors by diagonal) Then swap rows or columns by the middle row or middle column.

### Transpose a Matrix in-place

Transposing a matrix, we want to swap the matrix[i][j] by matrix[j][i] once. So we can iterate the bottom half or the top half of the matrix.

``````void transposeMatrix(vector<vector<int>> &matrix) {
int N = matrix.size();
if (N == 0) return;
assert(matrix.size() == N); // make sure it is NxN
for (int r = 0; r < N; ++ r) {
for (int c = 0; c < r; ++ c) { // bottom half
swap(matrix[r][c], matrix[c][r]);
}
}
}
``````

We don't need to do anything to the elements in the matrix diagonal since it won't make a difference.

### Rotate a Matrix in Place 90 degree clockwise

With the transposed matrix we have the following:

``````vector<vector<int>> matrix({
{1, 4, 7},
{2, 5, 8},
{3, 6, 9}
});
``````

Now, we can observe that we simply need to swap the colums by the centeral column:

``````void rotateClockwise(vector<vector<int>> &matrix) {
int N = matrix.size();
if (N == 0) return;
assert(matrix.size() == N); // make sure it is NxN

transposeMatrix(matrix);
for (int r = 0; r < N; ++ r) {
for (int c = 0; c < N / 2; ++ c) {
swap(matrix[r][c], matrix[r][N - c - 1]);
}
}
}
``````

### Rotate a Matrix in Place 90 degree Anti-clockwise

Similarly, we can swap the rows in order to make:

``````vector<vector<int>> matrix({
{3, 6, 9},
{2, 5, 8},
{1, 4, 7}
});
``````
``````void rotateAntiClockwise(vector<vector<int>> &matrix) {
int N = matrix.size();
if (N == 0) return;
assert(matrix.size() == N); // make sure it is NxN

transposeMatrix(matrix);
for (int r = 0; r < N / 2; ++ r) {
for (int c = 0; c < M; ++ c) {
swap(matrix[r][c], matrix[N - r - 1][c]);
}
}
}
``````

### Test Cases for Rotating Matrix

• Empty {{}}
• Single Element
• Identity Matrics
• Sparse Matrics
• Elements in one half (bottom or top)

The time complexity for all above implementations are O(N^2) and the space requirement is O(1) constant since we are doing it in-place without allocating new space.

--EOF (The Ultimate Computing & Technology Blog) --

Reposted to Computing Technology

Follow me for topics of Algorithms, Blockchain and Cloud.
I am @justyy - a Steem Witness
https://steemyy.com

Steem On!~
Every little helps! I hope this helps!

If you like my work, please consider voting for me or Buy Me a Coffee, thanks!
https://steemit.com/~witnesses type in justyy and click VOTE Alternatively, you could proxy to me if you are too lazy to vote!

Also: you can vote me at the tool I made: https://steemyy.com/witness-voting/?witness=justyy

STEEM 0.16
TRX 0.03
JST 0.026
BTC 12892.46
ETH 396.32
USDT 1.00
SBD 0.99