Rotating a Square Matrix Clockwise by 90 Degrees
Rotating a Square Matrix Clockwise by 90 Degrees
Rotating a square n×n matrix of integers clockwise by 90 degrees is a common programming challenge. This transformation must be performed in-place, meaning the rotation should not involve allocating a new 2D matrix.
Problem Statement
You are given an n×n matrix, represented as a list of lists. The task is to rotate this matrix 90 degrees clockwise, modifying the input matrix directly.
For instance:
Example 1
Input: matrix = [
[1,2],
[3,4]
]
Output: [
[3,1],
[4,2]
]
Explanation:
Explanation:
The range [0, 3] contains the numbers {0, 1, 2, 3}. The number 0 is missing from the array nums.
Example 2
Input: matrix = [
[1,2,3],
[4,5,6],
[7,8,9]
]
Output: [
[7,4,1],
[8,5,2],
[9,6,3]
]
Constraints
- n == matrix.length == matrix[i].length
- 1 <= n <= 20
- -1000 <= matrix[i][j] <= 1000
There are mainly three approach to solve this problem –
- Brute Force
- Rotate By Four Cells
- Reverse And Transpose
1. Brute Force
- Time complexity:
- Space complexity:
Python
C++
Java
JavaScript
Python
class Solution:
def rotate(self, matrix: List[List[int]]) -> None:
n = len(matrix)
rotated = [[0] * n for _ in range(n)]
for i in range(n):
for j in range(n):
rotated[j][n - 1 - i] = matrix[i][j]
for i in range(n):
for j in range(n):
matrix[i][j] = rotated[i][j]
C++
class Solution {
public:
void rotate(vector>& matrix) {
int n = matrix.size();
vector> rotated(n, vector(n));
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
rotated[j][n - 1 - i] = matrix[i][j];
}
}
matrix = rotated;
}
};
Java
public class Solution {
public void rotate(int[][] matrix) {
int n = matrix.length;
int[][] rotated = new int[n][n];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
rotated[j][n - 1 - i] = matrix[i][j];
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
matrix[i][j] = rotated[i][j];
}
}
}
}
JavaScript
class Solution {
/**
* @param {number[][]} matrix
* @return {void}
*/
rotate(matrix) {
const n = matrix.length;
const rotated = Array.from({ length: n }, () =>
Array(n).fill(0));
for (let i = 0; i < n; i++) {
for (let j = 0; j < n; j++) {
rotated[j][n - 1 - i] = matrix[i][j];
}
}
for (let i = 0; i < n; i++) {
for (let j = 0; j < n; j++) {
matrix[i][j] = rotated[i][j];
}
}
}
}
2. Rotate By Four Cells
Time & Space Complexity
- Time complexity: O(n^2)
- Space complexity: O(1)
Code
C++
Java
Python
JavaScript
C++
class Solution {
public:
void rotate(vector>& matrix) {
int l = 0;
int r = matrix.size() - 1;
while ( l < r ) {
for(int i = 0; i < r - l; i++) {
int top = l;
int bottom = r;
//save the topleft
int topLeft = matrix[top][l + i];
//move bottom left into top left
matrix[top][l + i] = matrix[bottom - i][l];
// move bottom right into bottom left
matrix[bottom - i][l] = matrix[bottom][r - i];
// move top right into bottom right
matrix[bottom][r - i] = matrix[top + i][r];
// move top left into top right
matrix[top + i][r] = topLeft;
}
r--;
l++;
}
}
};
Java
public class Solution {
public void rotate(int[][] matrix) {
int l = 0;
int r = matrix.length - 1;
while ( l < r ) {
for(int i = 0; i < r - l; i++) {
int top = l;
int bottom = r;
//save the topleft
int topLeft = matrix[top][l + i];
//move bottom left into top left
matrix[top][l + i] = matrix[bottom - i][l];
// move bottom right into bottom left
matrix[bottom - i][l] = matrix[bottom][r - i];
// move top right into bottom right
matrix[bottom][r - i] = matrix[top + i][r];
// move top left into top right
matrix[top + i][r] = topLeft;
}
r--;
l++;
}
}
}
Python
class Solution:
def rotate(self, matrix: List[List[int]]) -> None:
l, r = 0, len(matrix) - 1
while l < r:
for i in range(r - l):
top, bottom = l, r
# save the topleft
topLeft = matrix[top][l + i]
# move bottom left into top left
matrix[top][l + i] = matrix[bottom - i][l]
# move bottom right into bottom left
matrix[bottom - i][l] = matrix[bottom][r - i]
# move top right into bottom right
matrix[bottom][r - i] = matrix[top + i][r]
# move top left into top right
matrix[top + i][r] = topLeft
r -= 1
l += 1JavaScript
class Solution {
/**
* @param {number[][]} matrix
* @return {void}
*/
rotate(matrix) {
let l = 0;
let r = matrix.length - 1;
while (l < r) {
for (let i = 0; i < r - l; i++) {
const top = l;
const bottom = r;
// save the topleft
const topLeft = matrix[top][l + i];
// move bottom left into top left
matrix[top][l + i] = matrix[bottom - i][l];
// move bottom right into bottom left
matrix[bottom - i][l] = matrix[bottom][r - i];
// move top right into bottom right
matrix[bottom][r - i] = matrix[top + i][r];
// move top left into top right
matrix[top + i][r] = topLeft;
}
r--;
l++;
}
}
}3. Reverse And Transpose
- Time complexity: O(n^2)
- Space complexity: O(1)
Code
C++
Java
Python
JavaScript
C++
class Solution {
public:
void rotate(vector>& matrix) {
// Reverse the matrix vertically
reverse(matrix.begin(), matrix.end());
// Transpose the matrix
for (int i = 0; i < matrix.size(); ++i) {
for (int j = i + 1; j < matrix[i].size(); ++j)
swap(matrix[i][j], matrix[j][i]);
}
}
};
Java
public class Solution {
public void rotate(int[][] matrix) {
// Reverse the matrix vertically
reverse(matrix);
// Transpose the matrix
for (int i = 0; i < matrix.length; i++) {
for (int j = i; j < matrix[i].length; j++) {
int temp = matrix[i][j];
matrix[i][j] = matrix[j][i];
matrix[j][i] = temp;
}
}
}
private void reverse(int[][] matrix) {
int n = matrix.length;
for (int i = 0; i < n / 2; i++) {
int[] temp = matrix[i];
matrix[i] = matrix[n - 1 - i];
matrix[n - 1 - i] = temp;
}
}
}
Python
class Solution:
def rotate(self, matrix: List[List[int]]) -> None:
# Reverse the matrix vertically
matrix.reverse()
# Transpose the matrix
for i in range(len(matrix)):
for j in range(i + 1, len(matrix)):
matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]JavaScript
class Solution {
/**
* @param {number[][]} matrix
* @return {void}
*/
rotate(matrix) {
// Reverse the matrix vertically
matrix.reverse();
// Transpose the matrix
for (let i = 0; i < matrix.length; i++) {
for (let j = i; j < matrix[i].length; j++) {
[matrix[i][j], matrix[j][i]] = [matrix[j][i], matrix[i][j]];
}
}
}
}
