Problem
You are given an
n x n
2Dmatrix
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.
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:
$$ \Huge \begin{array}{|c|c|c|} \hline \colorbox{red} 1 & \colorbox{red} 2 & \colorbox{red}3 \\ \hline \colorbox{green} 4 & \colorbox{green} 5 & \colorbox{green}6 \\ \hline \colorbox{blue} 7 & \colorbox{blue} 8 & \colorbox{blue}9 \\ \hline \end{array} \Longrightarrow \begin{array}{|c|c|c|} \hline \colorbox{blue} 7 & \colorbox{green} 4 & \colorbox{red} 1 \\ \hline \colorbox{blue} 8 & \colorbox{green} 5 & \colorbox{red} 2 \\ \hline \colorbox{blue} 9 & \colorbox{green} 6 & \colorbox{red} 3 \\ \hline \end{array} $$
|
|
Example 2:
$$ \Huge \begin{array}{|c|c|c|c|} \hline \colorbox{red} 5 & \colorbox{red} 1 & \colorbox{red} 9 & \colorbox{red} {11}\\ \hline \colorbox{green} 2 & \colorbox{green} 4 & \colorbox{green} 8 & \colorbox{green} {10} \\ \hline \colorbox{blue} {13} & \colorbox{blue} 3 & \colorbox{blue} 6 & \colorbox{blue} 7 \\ \hline \colorbox{orange} {15} & \colorbox{orange} {14} & \colorbox{orange} {12} & \colorbox{orange} {16} \\ \hline \end{array} \Longrightarrow \begin{array}{|c|c|c|c|} \hline \colorbox{orange} {15} & \colorbox{blue} {13} & \colorbox{green} 2 & \colorbox{red} 5\\ \hline \colorbox{orange} {14} & \colorbox{blue} 3 & \colorbox{green} 4 & \colorbox{red} 1\\ \hline \colorbox{orange} {12} & \colorbox{blue} 6 & \colorbox{green} 8 & \colorbox{red} 9 \\ \hline \colorbox{orange} {16} & \colorbox{blue} 7 & \colorbox{green} {10} & \colorbox{red} {11} \\ \hline \end{array} $$
|
|
Solution
Consider the matrix from example 2 follow the dry run.
Video explanation
Here is the video explaining below methods in detail. Please check it out:
Method 1 - Naive approach using a copy matrix
Intuition
The simplest way to understand matrix rotation is to think of the movement of elements in columns to rows. For a rotated matrix:
- The first row of the original matrix becomes the last column in the rotated version.
- The second row becomes the second-last column, and so on.
This can be achieved easily by creating a copy matrix to store the rotated version. Then, copy this rotated matrix back into the original matrix to satisfy the “in-place” requirement.
Approach
- Create a new matrix to store the rotated version.
- Use two nested loops to map the positions of each element:
- The element at
matrix[i][j]
moves to the positionrotated[j][n - 1 - i]
.
- The element at
- Copy the rotated matrix back to the original matrix.
Code
|
|
|
|
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 - Four swap technique - layered looping
Intuition
Matrix rotation can also be viewed as a layer-by-layer process:
- Each layer of the matrix resembles a square ring.
- Elements move clockwise within the ring:
- Top → Right → Bottom → Left → Top.
- By performing these swaps one element at a time, the rotation is achieved without extra space.
Approach
- Identify concentric layers in the matrix (e.g., outermost layer, 2nd layer, etc.).
- For each layer:
- Iterate over the top row of the layer (
i
indexes the columns). - For each element in the top row:
- Perform four swaps:
- Top element → Right column.
- Right column → Bottom row.
- Bottom row → Left column.
- Left column → Top row.
- Perform four swaps:
- Iterate over the top row of the layer (
- Repeat for all layers until the entire matrix is rotated.
Code
|
|
|
|
Complexity
- ⏰ Time complexity:
O(n^2)
- 🧺 Space complexity:
O(1)
Method 3 - Four swap technique - different looping
This example is taken from here. Here is the basic algo:
- Iterate over the 2D array with i and j iterators to the size of N/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:
|
|
that means we have to save matrix[i][j]
to to temp variable, before updating it with matrix[n-1-j][i]
Code
|
|
Complexity
- ⏰ Time complexity:
O(n^2)
- 🧺 Space complexity:
O(1)
Dry Run
So, to sum up we were doing this:
|
|
then we rotate the following diamond which is sort of askew
|
|
and then the 2nd skewed diamond
|
|
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)
|
|
so now let’s figure out the indices of each layer, assume we always work with the outermost layer, we are doing
|
|
so on and so onuntil we are halfway through the edge so in general the pattern is
|
|
Can we do better. It may not look obvious, but yes we can. Here is the next solution:
Method 4 - Using Transpose and Reverse
Intuition
Rotating a matrix is equivalent to transposing it (converting rows into columns) followed by reversing each row:
- Transpose rearranges the matrix by swapping
matrix[i][j]
withmatrix[j][i]
, making rows into columns. (You can read more here: Transpose of a Matrix.) - Reversing rows aligns the columns into their proper clockwise-rotated order.
This method is both intuitive and simple, breaking the problem into two manageable steps.
Approach
- Transpose the matrix:
- Swap elements above the diagonal (
matrix[i][j]
↔matrix[j][i]
wherej > i
).
- Swap elements above the diagonal (
- Reverse each row:
- For each row, reverse its elements in place (swap elements symmetrically from start to end).
Here is how it will work (as gif):
Or if you prefer to watch silent video:
Code
|
|
|
|
Complexity
- ⏰ Time complexity:
O(n^2)
- 🧺 Space complexity:
O(1)
Method 5 - 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:
|
|
If your Matrix already implements this interface, then it can be rotated via a decorator class like this:
|
|
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!