LeetCode Rotate Image: In Place Swap

Overview

LeetCode Rotate Image could be solved by in place swap:  3 passes to swap the portion from 0 to n – 2 between top and right, bottom, left spirally and recursively,

LeetCode Rotate Image:

You are given an n x n 2D matrix representing an image.

Rotate the image by 90 degrees (clockwise).

Follow up:
Could you do this in-place?

Solution: In Place Swap

The key point to the solution is to use a recursive function to deal with the outer most loop. Consider the following

[
 [ 1, 2, 3 ],
 [ 8, 9, 4 ],
 [ 7, 6, 5 ]
]

so the outer loop is 1 2 3 4 5 6 7 8, you rotate this by 90 degrees clockwise by using swap in-place (don’t need any additional memory), then it would be

[
 [ 7, 8, 1 ],
 [ 6, 9, 2 ],
 [ 5, 4, 3 ]
]

After this is done, you rotate the inner loop recursively. This is quite similar to the solution of “Spiral Matrix”. We need 3 such passes to swap between top with the right edge (the last column) first, and then swap top (the first row) with the bottom (the last row), and finally, we swap the top and the left edge (the first column). The detailed implementation is listed as follows and it is accepted by LeetCode OJ to pass this Rotate Image problem:

void rotateInner(vector<vector<int>> &matrix, int s, int len) {
    if (len < 2)
        return ;

    for (int j = s + len - 2; j >= s; --j) {
        swap(matrix[s][j], matrix[j][s + len - 1]);
    }
    for (int j = s + len - 2; j >= s; --j) {
        swap(matrix[s][j], matrix[s + len - 1][s + len - 1 - j + s]);
    }
    for (int j = s + len - 2; j >= s; --j) {
        swap(matrix[s][j], matrix[s + len - 1 - j + s][s]);
    }
    rotateInner(matrix, s + 1, len - 2);
}

void rotate(vector<vector<int> > &matrix) {
    int n = matrix.size();
    if (n < 2) return ;
    rotateInner(matrix, 0, n);
}

Another different solution would involves more sophisticated thinking: firstly, we flip the matrix upside down, and then we flip the matrix by putting the bottom edge to the right (swap the top right triangle portion of the matrix and the bottom left triangle portion). This gives the following code:

void rotate(vector<vector<int> > &matrix)
{
     int n = matrix.size();
     if (n < 2) return ;
     reverse(matrix.begin(), matrix.end());
     for (int i = 0; i < n; ++i)
         for (int j = i+1; j < n; ++j)
             swap (matrix[i][j], matrix[j][i]);
}

Summary

LeetCode Rotate Image could be solved by in place swap:  3 passes to swap the portion from 0 to n – 2 between top and right, bottom, left spirally and recursively,

Written on May 20, 2013