Data Structures & Algorithms in Java – Matrix – Rotate Image

Problem:

Given a n * n matrix representing an image , rotate the matrix by 90 degrees .

Constraints:

Do not use any extra memory in proportion to the input size.

That is , space complexity should be 1.

For example,

For the input :

[ [1,2,3],

[4,5,6],

[7,8,9]]

The output is :

[[7,4,1],

[8,5,2],

[9,6,3]]

Try out the solution here:

https://leetcode.com/problems/rotate-image/

Solution:

Hint:

Rotating the matrix by 90 degrees is the same as transposing it (flipping it along the diagonal) and reversing it.

Explanation:

Our solutions requires not to use additional memory.

But let’s first check how to solve this using additional memory.

If you notice the new position of each element by manually noting down the row and column position they all follow the below formula:

matrix[row][column] = matrix[number_of_rows – column-1][row]

For example in the output for a matrix of size 3 * 3 ,

matrix[0][1] = matrix[1][0]

That is first row (index 0) second column (index 1) is replaced by second row (index 1) (3-1-1) first column (index 0)

matrix[1][0] = matrix[2][1]

Second row first column is replaced by third row second column and so on.

So ,

You can create a new output matrix of the same size and assign each element according to this formula.

Here is the code:

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

Our solution though asks us not to use additional memory.

In that case ,

You can use the below strategy:

Here is the algorithm:

ALGORITHM:

STEP 1: For each row in the matrix and for each column starting from row + 1 value flip the elements by interchanging the rows and columns . This will flip the elements along the diagonal.

STEP 2: For each row in the matrix and for each column until half the number of columns , reverse the elements by changing the column value of elements in the first half to the corresponding position in the later half. This will reverse the elements.

Here is the code:

Code:

class Solution {
    public void rotate(int[][] matrix) {
        
        
        int noOfRows = matrix.length ;
        int noOfCols = matrix[0].length;
        
        
        //transpose
        
        for(int i=0;i<noOfRows;i++){
            
            
            
            for(int j=i;j<noOfCols;j++){
                
                
                int temp = matrix[i][j];
                
                matrix[i][j] = matrix[j][i];
                
                matrix[j][i] = temp;
            }
        }
        
        
        //reverse
        
        for(int i=0;i<noOfRows;i++){
            
            
            for(int j=0;j<noOfCols/2;j++){
                
                
                int temp = matrix[i][j];
                
                matrix[i][j] = matrix[i][noOfRows - j - 1];
                
                matrix[i][noOfRows-j-1] = temp;
            }
        }
  
    }
}

For transposing , we traverse along the rows from the start but along the columns starting from row + 1 value because we want only the elements after the diagonal.

Along the diagonal both row and column indexes match. So we take all the elements after row +1 column value and flip them with those in the other side of the diagonal.

As shown in the above diagram , you pick only those elements to the right of diagonal. (You can also pick elements to the left of the diagonal and flip them – both are the same)

For reversing you pick up elements until the half side of the matrix and flip them with the corresponding elements in the other half . That is why we traverse until half the number of columns ( j < noOfCols/2) in the code.

Time complexity is O(n) where n is the number of elements in the matrix since we iterate through all the elements in the two for loops O(n) +O(n) = O(n)

Space complexity is O(1) since we don’t use additional memory and rotate the matrix in place.

That’s it!