DEV Community

sachin26
sachin26

Posted on

Striver's SDE Sheet Journey - #7 Rotate Image

Problem Statement :-

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

Example 1:

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

Rotate Image

after rotating by 90 degree,

Rotate Image

Solution 1

from the above images, you can see, after the rotation, the first row of the matrix has turned into the last column of the matrix and the second row of the matrix has turned into the second last column, and so on.

so what we are going to do is, initialize one more matrix rotated and copy the first row from the original matrix to the last column of the new matrix rotated, and so on.

step-1 initialize a n*n size of matrix rotate.

step-2 run a loop from i=0 to n

1. run another loop from j=0 to n.

2. copy matrix values to the last column of rotate matrix.
rotated[j][n-i-1] = matrix[i][j]

step-3 end.

Java

class Solution {
    public void rotate(int[][] matrix) {

        int n = matrix.length;  
        int rotated[][] = new int[n][n];

        for (int i = 0; i < n; i++) {

            for (int j = 0; j < n; j++) {

                rotated[j][n - i - 1] = matrix[i][j];
            }
        }


        for(int i=0; i<n;i++)
        System.out.println(Arrays.toString(rotated[i]));
    }
}
Enter fullscreen mode Exit fullscreen mode

Time Complexity : O(n*n),bcoz we are running two loops.

space Complexity : O(n*n),initialising a new n*n matrix.

Solution 2

if you observed the first row of the output, is nothing, just the reverse of the first column.

for the expected output, first, we have to transpose the matrix and then reverse each row of the matrix.

lets understand it in a visual way.

rotate
step-1 transpose the matrix. (changing rows to columns & columns to rows)

rotate image

step-2 reverse each row of the matrix.

rotate image

Java

class Solution {
    public void rotate(int[][] matrix) {

        int n = matrix.length;

        // transpose the matrix
       for(int i=0; i< n;i++){

            for(int j=0; j<i; j++){

               swap(matrix,i,j);
            }
        }


        // reverse rows
        for(int i=0; i<n;i++){

           reverse(matrix[i],n);
        }

    }

    private void swap(int[][] matrix,int i, int j){
            int temp = matrix[i][j];
            matrix[i][j] = matrix[j][i];
            matrix[j][i] = temp;
    }

    private void reverse(int[] row,int n){

        for(int i=0; i<n/2;i++){
            int temp = row[i];
            row[i] = row[n-i-1];
            row[n-i-1] = temp;
        }
    }


}
Enter fullscreen mode Exit fullscreen mode

Time Complexity : transposing the matrix + reversing each row of the matrix,then O(n*n) + O(n*n).

space Complexity : in this case we are not using any extra space,then O(1).

Thank you for reading this article I hope I explained it clearly.

Top comments (2)

Collapse
 
ashutosh049 profile image
ashutosh049 • Edited

Thanks! Aren't there any more efficient algo for matrix operation? What about Strasen's one. You can check if he proposed some better to quadratic. Not sure about that. How about this(taken from quad trees):

rotate(qt) {
  if ( isValue(qt) )
  return qt
  else return makeQT( rotate(rl(qt)), rotate(ll(qt)),
  rotate(ru(qt)), rotate(lu(qt)) )
}
Enter fullscreen mode Exit fullscreen mode

Quad trees are interesting thing to read.

Collapse
 
sachin26 profile image
sachin26

thanks for sharing about interesting algos. I will read.