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 :

Given input matrix = 
[
  [1,2,3],
  [4,5,6],
  [7,8,9]
],

Rotate the input matrix in-place such that it becomes:
[
  [7,4,1],
  [8,5,2],
  [9,6,3]
]

The following figure is a pictorial representation of the rotation process:

Transpose and then Reverse:

The obvious idea would be to transpose the matrix first and then reverse each row. This simple approach already demonstrates the best possible time complexity O(n2).

Transpose of a Matrix

Transpose is a matrix formed by swapping the rows into columns and vice-versa. The new matrix obtained by interchanging the rows and columns of the original matrix is called the transpose of the matrix. If A = [aij] be an m × n matrix, then the matrix obtained by interchanging the rows and columns of A would be the transpose of A. of It is denoted by A′ or (AT). In other words, if A = [aij]mxn ,then A′ = [aji]nxm . For example, check the following figure as a pictorial representation of transpose of a matrix.

Now to solve the problem we have to Transpose the matrix first and then reverse each row

Java Code

class MatrixSolution {

    public void rotateMatrix(int[][] matrix) {
        transpose(matrix);
        System.out.println("Matrix After Transpose");
        print(matrix);
        reverse(matrix);
    }

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

    private void reverse(int[][] matrix) {
        for (int[] arr : matrix) {
            for (int i = 0, j = matrix.length - 1; i < j; i++, j--) {
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }
    }

    public void print(int[][] matrix) {
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[i].length; j++) {
                System.out.print(matrix[i][j] + " ");
            }
            System.out.println();
        }
    }
}

public class RotateMatrix {

    public static void main(String[] args) {
        int[][] matrix = {
                {1, 2, 3},
                {4, 5, 6},
                {7, 8, 9}
        };
        MatrixSolution matrixSolution = new MatrixSolution();
        System.out.println("Matrix Before Rotation>>");
        matrixSolution.print(matrix);
        matrixSolution.rotateMatrix(matrix);
        System.out.println("Matrix After 90 Degree Rotation>>");
        matrixSolution.print(matrix);
    }
}

The output of the program:

Matrix Before Rotation:
1 2 3 
4 5 6 
7 8 9 

Matrix After Transpose:
1 4 7 
2 5 8 
3 6 9 

Matrix After 90 Degree Rotation:
7 4 1 
8 5 2 
9 6 3 
  • Time complexity: O(N2).
  • Space complexity: O(1) since we do a rotation in place

Categories: 2D Array

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s