Rotate Image


You are given an n x n 2D matrix representing an image and you are required to rotate the image by 90 degrees (clockwise). The image must be rotated in place. You are not suppose to create a new array and do rotation on it.

 

Example

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

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

 

Approach

On keen observation you can notice that the first column of the original matrix is the reverse of the first row of the rotated matrix. Hence, the solution could be as simple as transpose the matrix and then reverse each row.

Transpose of a matrix is the matrix obtained by interchanging its rows into columns or columns into rows.

 

Step 1: Transpose the matrix.
  1. Let the matrix be mat[a][b] and loop through the original array and convert its rows to the columns of matrix.
  2. Declare 2 variables i and j.
  3. Set both i,j=0
  4. Repeat until i<b
  1. Repeat until j<a
  2. Interchange the values of mat[i][j] and mat[j][i]
  3. j=j+1
  1. i=i+1
Step 2: Reverse each row of the matrix.
  1. Declare 2 variables i and j.
  2. Set both i,j=0
  3. Repeat until i<b
  1. Repeat until j<b/2
  2. Interchange the values of mat[j][i] and mat[i][b-1-j]
  3. j=j+1
  1. i=i+1

 

Complexity

  • Time Complexity:  O(N*N) + O(N*N)
    One O(N*N) is for transposing the matrix and the other is for reversing the matrix.
  • Space Complexity: O(1)

 

Code

# Java Code

import java.util.*;

class MatrixRotator {
    static void rotateMatrixClockwise(int[][] matrix) {
        // Transpose the matrix
        for (int row = 0; row < matrix.length; row++) {
            for (int col = row; col < matrix[0].length; col++) {
                int temp = matrix[row][col];
                matrix[row][col] = matrix[col][row];
                matrix[col][row] = temp;
            }
        }

        // Reverse each row
        for (int row = 0; row < matrix.length; row++) {
            for (int col = 0; col < matrix.length / 2; col++) {
                int temp = matrix[row][col];
                matrix[row][col] = matrix[row][matrix.length - 1 - col];
                matrix[row][matrix.length - 1 - col] = temp;
            }
        }
    }

    public static void main(String args[]) {
        int inputMatrix[][] = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};
        rotateMatrixClockwise(inputMatrix);

        System.out.println("Rotated Matrix:");
        for (int row = 0; row < inputMatrix.length; row++) {
            for (int col = 0; col < inputMatrix[0].length; col++) {
                System.out.print(inputMatrix[row][col] + " ");
            }
            System.out.println();
        }
    }
}
Output

Rotated Matrix:

7 4 1

8 5 2

9 6 3



Thanks for feedback.



Read More....
Find the no of islands in a 2D Array/Matrix
3 Sum
4 Sum - Find four elements that sum to a given target value
Chocolate Distribution Problem
Find the missing number in a sorted array
Best Time to Buy and Sell Stock