Rotate Image

Rotate a matrix clockwisely for 90 degree. Two ways to do this.

Let the vertical axis to be X and horizontal axis to be Y, the size of matrix is n. After rotation, the value of a cell x, y will go to n - y, x. To achieve this, we can first flip the matrix arround the diagonal from top left to bottom right and get y, x. Then we flip parallel Y in the middle of the matrix to get n - y, x.

public class RotateImage {
    private void swap(int[][] matrix, int ax, int ay, int bx, int by) {
        int t = matrix[ay][ax];
        matrix[ay][ax] = matrix[by][bx];
        matrix[by][bx] = t;
    }

    public void rotate(int[][] matrix) {
        int n = matrix.length;
        if (n == 0) return;

        for (int y = 0; y < n; y++) {
            for (int x = y + 1; x < n; x++) {
                swap(matrix, x, y, y, x);
            }
        }

        for (int y = 0; y < n; y++) {
            for (int x = 0; x < n / 2; x++) {
                swap(matrix, x, y, n - x - 1, y);
            }
        }
    }
}

Conversely, if we'd like to rotate counterclockwisely, we need to transform x, y to y, n - x. So first we get y, x like what we do above, then, in the last step we flip the matrix parallel to X axis in the middle.

There are another way to do such rotation. Take clockwise as example, value at x, y will go to n - y, x, value at n - y, x will go to n - x, n - y, value at n - x, n - y will go to y, n - x and value at y, n - x will go to x, y.

To apply this swap cycle in place, we can first move x, y to y, n - x, then to n - x, n - y and finally get to n - y, x. After three swaps like this, we will get all these four values in where it should be at last.

public class RotateImage {
    private void swap(int[][] matrix, int ax, int ay, int bx, int by) {
        int t = matrix[ay][ax];
        matrix[ay][ax] = matrix[by][bx];
        matrix[by][bx] = t;
    }

    public void rotate(int[][] matrix) {
        int n = matrix.length;
        if (n == 0) return;

        for (int y = 0; y < n / 2; y++) {
            for (int x = y; x < n - y - 1; x++) {
                swap(matrix, x, y, y, n - x - 1);
                swap(matrix, y, n - x - 1, n - x - 1, n - y - 1);
                swap(matrix, n - x - 1, n - y - 1, n - y - 1, x);
            }
        }
    }
}