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[0].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[0].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[0].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

Coin Marketplace

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