[LeetCode] Rotate Image

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: It is easy to derive that (i, j) -> (j, n - 1 - i) -> (n - 1 - i, n - 1 - j) -> (n - 1 - j, i), where the range of i is [0, n/2), while the range of j is [i, n - 1 - i).
Alternatively, one can visualize this layer by layer. We first do this for the out-most layer, where we are rotating n - 1 elements (not n elements) of each of the top-most row, the right-most column, the bottom-most row, and the left-most column. And we conduct this element-wise by only using one extra temporary variable. After this is done, one may view it as a sub-problem of size (n - 1) x (n - 1), which can be solved in a similar manner.

public class Solution {
    public void rotate(int[][] matrix) {
        int n = matrix.length;
        for (int i = 0; i < n / 2; i++) {
            for (int j = i; j < n - 1 - i; j++) {
                int tmp = matrix[i][j];
                matrix[i][j] = matrix[n - 1 - j][i];
                matrix[n - 1 - j][i] = matrix[n - 1 - i][n - 1 - j];
                matrix[n - 1 - i][n - 1 - j] = matrix[j][n - 1 - i];
                matrix[j][n - 1 - i] = tmp;
            }
        }
        return;
    }
}