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 😄