Sahil Bondre

Posted on

# Interview Prep #6: Rotate Image

## 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 ðŸ˜„

Aleksandr Hovhannisyan

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 #`i` becomes Column #`n-i+1`.

But we can make things easier for ourselves by switching up our perspective:

``````1 2 3
4 5 6
7 8 9
``````

Algorithm:

For `col = 0` through `n - 1`:

Iterate through the rows in reverse: `row = n - 1 through 0` and fill the new matrix with `original[row][col]`

``````7 4 1
8 5 2
9 6 3
``````

Sahil Bondre

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.