48. Rotate Image

Problem Statement

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. (link)

Example 1:

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

Example 2:

Input: matrix = [[5,1,9,11],[2,4,8,10],[13,3,6,7],[15,14,12,16]]
Output: [[15,13,2,5],[14,3,4,1],[12,6,8,9],[16,7,10,11]]

Constraints:

• n == matrix.length == matrix[i].length

• 1 <= n <= 20

• -1000 <= matrix[i][j] <= 1000

Solution

Brute force Approach (Extra Space)

Upon careful observation, we note that the initial row corresponds to the final column. Consequently, we create a new matrix of identical dimensions and populate its elements in a column-wise manner, starting from the last column.

---

(0,0) -> (0, n-1)

(0,1) -> (1, n-1)

(0,2) -> (2, n-1)

....

(0,n-1) -> (n-1, n-1)

---

(1,0) -> (0, n-2)

(1,1) -> (1, n-2)

(1,2) -> (2, n-2)

....

(1,n-1) -> (n-1, n-2)

---

The pattern we obtained from the information above is represented as (i, j) transforming into (j, n-1-i). These indicate the indices associated with the swapping process.

Time - O(n^2)

Space - O(n^2)

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

Optimal Approach

Whenever a matrix rotation is required, it is advisable to transpose the provided matrix and compare it with the original answer.

If any of the rows are found to be present as columns, then our default operation is to transpose.

Upon observation, we note that transposing the given array and reversing individual rows results in a matrix rotated by 90 degrees.

Transpose: The core logic of the transpose operation involves swapping the (i, j) element with the (j, i) element. If this operation is applied to each element of the matrix, the matrix remains unchanged because the swapping occurs on the same element twice, yielding no change. To address this, we initiate swapping only on half of the diagonal elements. The diagonal elements effectively divide the matrix into two halves, allowing us to apply swapping to either one. In the subsequent code, we exclusively iterate over the right half of the diagonal elements and execute the swap.

Time - O(n^2)

Space - O(1)

class Solution {
    public void rotate(int[][] matrix) {
        int n = matrix.length;
        for(int i=0; i<n; i++){
            for(int j=i+1; j<n; j++){
                transposeSwap(matrix, i, j);
            }
        }

        for(int i=0; i<n; i++){
            reverse(matrix[i]);
        }
    }

    public void transposeSwap(int[][] matrix, int i, int j){
        int temp = matrix[i][j];
        matrix[i][j] = matrix[j][i];
        matrix[j][i] = temp;
    }

    public void reverse(int[] row){
        int n = row.length;

        for(int i=0; i<n/2; i++){
            swap(row, i, n-1-i);
        }
    }

    public void swap(int[] row, int i, int j){
        int temp = row[i];
        row[i] = row[j];
        row[j] = temp;
    }
}