DEV Community

loading...

Interview Prep #6: Rotate Image

godcrampy profile image Sahil Bondre ・1 min read

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.

Matrix Rotation

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 😄

Discussion

pic
Editor guide
Collapse
aleksandrhovhannisyan profile image
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
Collapse
godcrampy profile image
Sahil Bondre Author

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.