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 (rotate a matrix), 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.
See also: Teaching Kids Programming – Rotate a 2D Matrix/Image 90 Degree Clockwise
–EOF (The Ultimate Computing & Technology Blog) —
loading...
Last Post: The Terminal Software Engineer Level
Next Post: Big O Simply Explained
