DSA
Rotate Matrix
Simulation approach — transpose + row-reverse. Time O(n²), Space O(1).
Practice here
You are given an n x n 2D matrix 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.
Simulation#
- Intuition: A 90° clockwise rotation maps element (i, j) to position (j, n-1-i). Rather than tracking this four-way cycle directly, the rotation can be decomposed into two simpler in-place operations: a transpose (which swaps rows and columns) followed by a horizontal reversal (which mirrors each row).
- Mechanics: The transpose swaps matrix[i][j] with matrix[j][i] for all j < i, converting rows into columns. Reversing each row then shifts columns from left-to-right order into right-to-left, completing the 90° clockwise effect. Both operations are done entirely in-place with no extra matrix.
- Trade-off: O(n²) time (every cell is visited at most twice) and O(1) auxiliary space. This is optimal since all n² elements must be moved. The two-step decomposition avoids the error-prone four-index cyclic swap that a direct rotation formula requires.
cpp
class Solution {
public:
void transpose(vector<vector<int>>& matrix){
for(int i=0;i<matrix.size();i++)
{
for(int j=0;j<i;j++)
{
swap(matrix[i][j], matrix[j][i]);
}
}
}
void reverseByRows(vector<vector<int>>& matrix){
for(int i=0;i<matrix.size();i++)
{
reverse(matrix[i].begin(), matrix[i].end());
}
}
void rotate(vector<vector<int>>& matrix) {
transpose(matrix);
reverseByRows(matrix);
}
};
## Follow Up
### How would your logic change if you were asked to rotate the matrix counter-clockwise using a similar two-step reflection method?
The same two-step idea applies — you just swap the order of the operations.
| Rotation | Step 1 | Step 2 |
|---|---|---|
| 90° **clockwise** | Transpose | Reverse each **row** |
| 90° **counter-clockwise** | Transpose | Reverse each **column** |
Reversing columns (instead of rows) after the transpose mirrors the matrix vertically, which is exactly the extra flip that turns a clockwise rotation into a counter-clockwise one.
```cpp
void rotateCounterClockwise(vector<vector<int>>& matrix) {
int n = matrix.size();
// Step 1: transpose (same as before)
for(int i = 0; i < n; i++)
for(int j = 0; j < i; j++)
swap(matrix[i][j], matrix[j][i]);
// Step 2: reverse each column (not each row)
for(int j = 0; j < n; j++) {
int top = 0, bot = n - 1;
while(top < bot)
swap(matrix[top++][j], matrix[bot--][j]);
}
}
Alternatively, you can skip the transpose entirely and just reverse each row followed by a transpose — the decompositions are symmetric. Both remain O(n²) time and O(1) space.