48. Rotate Image

/**

 * 48. Rotate Image

 * You are given an n x n 2D matrix representing an image, rotate the image by 90 degrees (clockwise).

 * You have to rotate the image in-place, which means you have to modify the input 2D matrix directly.

 * DO NOT allocate another 2D matrix and do the rotation.

 * Example 1:

 * Input: matrix = [[1,2,3],[4,5,6],[7,8,9]]

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

 */

See solution to the problem on github here: https://github.com/zcoderz/leetcode/blob/main/src/main/java/frequent/medium/RotateImage.java

This is a common interview question. I am explaining below two approaches for solving this problem.

Approach 1: this is straightforward:

1. First transpose the matrix (swap i,j with j,i).
2. Reflect columns in each row (for each row swap column j with n-j-1 where n is the number of columns).

Here is the code for Approach 1:

public void transpose(int[][] matrix) {
    int n = matrix.length;
    for (int i = 0; i < n; i++) {
        for (int j = i; j < n; j++) {
            int tmp = matrix[j][i];
            matrix[j][i] = matrix[i][j];
            matrix[i][j] = tmp;
        }
    }
}

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

Approach 2: This approach solves the problem in a single pass.

The algorithm is:

1. Create group of 4 cells that together form a transformation unit and rotate them.
2. Rotate each group of 4 cells until the matrix is transformed.

Leet code has a visual that makes understanding the below code simple. Coming up with this translation in an interview is hard. Its best to stick with the approach 1 in interview but understand the below approach for its extremely elegant.

Here is the code for Approach 2:

public void rotate4Groups(int[][] matrix) {
    int rowMax = matrix.length;
    for (int i =0; i < rowMax/2 + rowMax%2; i++) {
        for (int j = 0; j < rowMax/2; j++) {
            int tmp = matrix[i][j];
            matrix[i][j] = matrix[rowMax-j-1][i];
            matrix[rowMax-j-1][i] = matrix[rowMax-i-1][rowMax-j-1];
            matrix[rowMax-i-1][rowMax-j-1] = matrix[j][rowMax-i-1];
            matrix[j][rowMax-i-1] = tmp;
        }
    }
}