Leetcode 48. How to Rotate a Square Matrix
Rotate a square matrix 90 degrees clockwise in two steps: transpose and mirror vertically in place.
Problem statement
Given an n x n 2D matrix representing an image, your task is to rotate the image by 90 degrees clockwise. The rotation must be performed in-place, meaning you need to modify the original input 2D matrix directly. It is not allowed to create another 2D matrix for the rotation.
Example 1
Input: matrix = [[1,2,3],[4,5,6],[7,8,9]]
Output: [[7,4,1],[8,5,2],[9,6,3]]
Example 2
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]]
Constraints
n == matrix.length == matrix[i].length.1 <= n <= 20.-1000 <= matrix[i][j] <= 1000.
Solution: The math behind
For any square matrix, the rotation 90 degrees clockwise can be performed in two steps:
- Transpose the matrix.
- Mirror the matrix vertically.
Code
#include <iostream>
#include <vector>
using namespace std;
void rotate(vector<vector<int>>& matrix) {
const int n = matrix.size();
// transpose
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
swap(matrix[i][j], matrix[j][i]);
}
}
// vertical mirror
for (int i = 0; i < n; i++) {
for (int j = 0; j < n / 2; j++ ) {
swap(matrix[i][j], matrix[i][n - 1 - j]);
}
}
}
void printMatrix(const vector<vector<int>>& matrix) {
cout << "[";
for (auto& row: matrix) {
cout << "[";
for (auto& a: row) {
cout << a << ",";
}
cout << "],";
}
cout << "]\n";
}
int main() {
vector<vector<int>> matrix</span><span class="mi">1</span><span class="p">,</span><span class="mi">2</span><span class="p">,</span><span class="mi">3</span><span class="p">},{</span><span class="mi">4</span><span class="p">,</span><span class="mi">5</span><span class="p">,</span><span class="mi">6</span><span class="p">},{</span><span class="mi">7</span><span class="p">,</span><span class="mi">8</span><span class="p">,</span><span class="mi">9</span><span class="p">;
rotate(matrix);
printMatrix(matrix);
matrix = </span><span class="mi">5</span><span class="p">,</span><span class="mi">1</span><span class="p">,</span><span class="mi">9</span><span class="p">,</span><span class="mi">11</span><span class="p">},{</span><span class="mi">2</span><span class="p">,</span><span class="mi">4</span><span class="p">,</span><span class="mi">8</span><span class="p">,</span><span class="mi">10</span><span class="p">},{</span><span class="mi">13</span><span class="p">,</span><span class="mi">3</span><span class="p">,</span><span class="mi">6</span><span class="p">,</span><span class="mi">7</span><span class="p">},{</span><span class="mi">15</span><span class="p">,</span><span class="mi">14</span><span class="p">,</span><span class="mi">12</span><span class="p">,</span><span class="mi">16</span><span class="p">;
rotate(matrix);
printMatrix(matrix);
}
Output:
[[7,4,1,],[8,5,2,],[9,6,3,],]
[[15,13,2,5,],[14,3,4,1,],[12,6,8,9,],[16,7,10,11,],]
Complexity
- Runtime:
O(n^2), wheren = matrix.length. - Extra space:
O(1).
Implementation tips
-
The function
std::swapcan be used to exchange two values. -
When doing the transpose or mirroring, you could visit over only one-half of the matrix.
Exercise
Thanks for reading!
I hope you enjoyed this content. Don't keep it to yourself! Share it with your network and help each other improve your coding skills and advance your career!
Nhut Nguyen, the author of The Problem Solver's Guide To Coding.
Don't miss what's next. Subscribe to LeetSolve - Level Up Your Coding Skills: