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 😄
Top comments (2)
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 #ibecomes Column #n-i+1.But we can make things easier for ourselves by switching up our perspective:
Algorithm:
For
col = 0throughn - 1:Iterate through the rows in reverse:
row = n - 1 through 0and fill the new matrix withoriginal[row][col]Yea, your solution will work as well. It's just that it will take additional O(n2) space 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.