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

For example, original Matrix 3×3:

1
2
3
4
5

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

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

Rotating it 90 degree clockwise would make it:

1
2
3
4
5

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

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.

1
2
3
4
5
6
7
8
9
10

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]);
      }
   }
}

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:

1
2
3
4
5

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

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:

1
2
3
4
5
6
7
8
9
10
11
12

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]);
      }
   }
}

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:

1
2
3
4
5

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

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

1
2
3
4
5
6
7
8
9
10
11
12

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]);
      }
   }
}

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) —