Problem

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

Another way to ask the same problem

Given an image represented by an NxN matrix, where each pixel in the image is 4 bytes, write a method to rotate the image by 90 degrees. Can you do this in place?

Examples

Example 1:

$$ \begin{bmatrix} \colorbox{red} 1 & \colorbox{red} 2 & \colorbox{red}3 \\ \colorbox{green} 4 & \colorbox{green} 5 & \colorbox{green}6 \\ \colorbox{blue} 7 & \colorbox{blue} 8 & \colorbox{blue}9 \end{bmatrix} \Longrightarrow \begin{bmatrix} \colorbox{blue} 7 & \colorbox{green} 4 & \colorbox{red} 1 \\ \colorbox{blue} 8 & \colorbox{green} 5 & \colorbox{red} 2 \\ \colorbox{blue} 9 & \colorbox{green} 6 & \colorbox{red} 3 \end{bmatrix} $$

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

Example 2:

$$ \begin{bmatrix} \colorbox{red} 5 & \colorbox{red} 1 & \colorbox{red} 9 & \colorbox{red} {11}\\ \colorbox{green} 2 & \colorbox{green} 4 & \colorbox{green} 8 & \colorbox{green} {10} \\ \colorbox{blue} {13} & \colorbox{blue} 3 & \colorbox{blue} 6 & \colorbox{blue} 7 \\ \colorbox{orange} {15} & \colorbox{orange} {14} & \colorbox{orange} {12} & \colorbox{orange} {16} \end{bmatrix} \Longrightarrow \begin{bmatrix} \colorbox{orange} {15} & \colorbox{blue} {13} & \colorbox{green} 2 & \colorbox{red} 5\\ \colorbox{orange} {14} & \colorbox{blue} 3 & \colorbox{green} 4 & \colorbox{red} 1\\ \colorbox{orange} {12} & \colorbox{blue} 6 & \colorbox{green} 8 & \colorbox{red} 9 \\ \colorbox{orange} {16} & \colorbox{blue} 7 & \colorbox{green} {10} & \colorbox{red} {11} \end{bmatrix} $$

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]]

Solution

Consider the array

int[,] array = new int[4,4] {
 { 1,2,3,4 },
 { 5,6,7,8 },
 { 9,0,1,2 },
 { 3,4,5,6 }
};

Method 1 - Using Extra Space, a 2D Array of Same Size

Code

Java
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[i][j] = matrix[n - j - 1][i];
			}
		}

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

		return ans;
	}
}

Dry Run

Lets understand this by example. Consider the array :

Complexity

  • ⏰ Time complexity: O(n^2)
  • 🧺 Space complexity: O(n^2)

But as we are using lots of space, can we do better?

Method 2 - Without Using Any Extra Spaces but O(n^2)

This example is taken from here. Here is the basic algo:

  1. Iterate over the 2D array with i and j iterators to the size of N/2
  2. Now take the corner elements based on i and j, and swap them accordingly

This method is similar to method 1, we were doing this in method 1:

ret[i, j] = matrix[n - j - 1, i];

that means we have to save matrix[i][j] to to temp variable, before updating it with matrix[n-1-j][i]

Java Code

class Solution {

	public static void rotate(int[][] matrix) {
		int n = matrix.length; // Renamed N to n for clarity
		for (int i = 0; i < n / 2; ++i) {
			for (int j = 0; j<(n + 1) / 2; ++j) {
				int temp = matrix[i][j]; // save the top element;
				matrix[i][j] = matrix[n - 1 - j][i]; // right -> top;
				matrix[n - 1 - j][i] = matrix[n - 1 - i][n - 1 - j]; // bottom -> right;
				matrix[n - 1 - i][n - 1 - j] = matrix[j][n - 1 - i]; // left -> bottom;
				matrix[j][n - 1 - i] = temp; // top -> left;
			}
		}
	}

}

Complexity

  • ⏰ Time complexity: O(n^2)
  • 🧺 Space complexity: O(1)

Dry Run

So, to sum up we were doing this:

1 4

13 16

then we rotate the following diamond which is sort of askew


   2
           8
9      
       15

and then the 2nd skewed diamond


       3
5          
           12
   14

so that takes care of the outer edge so essentially we do that one shell at a time until finally the middle square (or if it’s odd just the final element which does not move)

6 7
10 11

so now let’s figure out the indices of each layer, assume we always work with the outermost layer, we are doing

[0,0] -> [0,n-1], [0,n-1] -> [n-1,n-1], [n-1,n-1] -> [n-1,0], and [n-1,0] -> [0,0]
[0,1] -> [1,n-1], [1,n-2] -> [n-1,n-2], [n-1,n-2] -> [n-2,0], and [n-2,0] -> [0,1]
[0,2] -> [2,n-2], [2,n-2] -> [n-1,n-3], [n-1,n-3] -> [n-3,0], and [n-3,0] -> [0,2]

so on and so onuntil we are halfway through the edge so in general the pattern is

[0,i] -> [i,n-i], [i,n-i] -> [n-1,n-(i+1)], [n-1,n-(i+1)] -> [n-(i+1),0], and [n-(i+1),0] to [0,i]

Can we do better. It may not look obvious, but yes we can. Here is the next solution:

Method 3 - Using Transpose and Reverse

This is the nice solution 🏆 when it comes to simplicity. This has 2 steps:

  1. Transpose the matrix (This is same as Transpose of a Matrix.)
  2. Swap the columns

Here is how it will work (as gif):

Or if you prefer to watch silent video:

Code

Java
public void rotate(int[][] matrix) {

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

public void reverseRows(int[][] matrix){
    for(int i = 0; i < matrix.length; i++){
        int n = matrix[i].length;
        for(int j = 0; j < n/2; j++){
            int temp = matrix[i][j];
            matrix[i][j] = matrix[i][n - j- 1];
            matrix[i][n - j - 1] = temp;
        }
    }
}

Complexity

  • ⏰ Time complexity: O(n^2)
  • 🧺 Space complexity: O(1)

Method 4 - Adding Decorator on the Top of Matrix

This method has been suggested by Drew here. Just keeping it here: Whilst rotating the data in place might be necessary (perhaps to update the physically stored representation), it becomes simpler and possibly more performant to add a layer of indirection onto the array access, perhaps an interface:

interface IReadableMatrix {
 int GetValue(int x, int y);
}

If your Matrix already implements this interface, then it can be rotated via a decorator class like this:

class RotatedMatrix: IReadableMatrix {
    private readonly IReadableMatrix _baseMatrix;

    public RotatedMatrix(IReadableMatrix baseMatrix) {
        _baseMatrix = baseMatrix;
    }

    int GetValue(int x, int y) {
        // transpose x and y dimensions
        return _baseMatrix(y, x);
    }
}

Rotating +90/-90/180 degrees, flipping horizontally/vertically and scaling can all be achieved in this fashion as well. Performance would need to be measured in your specific scenario. However the O(n^2) operation has now been replaced with an O(1) call. It’s a virtual method call which is slower than direct array access, so it depends upon how frequently the rotated array is used after rotation. If it’s used once, then this approach would definitely win. If it’s rotated then used in a long-running system for days, then in-place rotation might perform better. It also depends whether you can accept the up-front cost. As with all performance issues, measure, measure, measure!