Leetcode 48 Rotate Image
Rotate Image – LeetCode
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
This is an interesting problem which looks complex but essentially there are just 2 steps we need to do this.
- Reverse each row
- Mirror the matrix based on the diagonal line from bottom left corner to top right corner
Solution
Javascript:
/**
* @param {number[][]} matrix
* @return {void} Do not return anything, modify matrix in-place instead.
*/
var rotate = function(matrix) {
let n = matrix.length
// reverse each row
for(let i = 0; i < n; i++) {
let left = 0;
let right = n - 1;
while(left < right) {
let temp = matrix[i][left];
matrix[i][left] = matrix[i][right];
matrix[i][right] = temp;
left++;
right--;
}
}
// mirror the matrix based on the diagonal line from (n - 1, 0) to (0, n - 1)
let rotatedMap = {};
for(let i = 0; i < n; i++) {
for(let j = 0; j < n; j++) {
if(!rotatedMap[`${i}-${j}`]) {
let temp = matrix[i][j];
matrix[i][j] = matrix[n - 1 - j][n - 1 -i];
matrix[n - 1 - j][n - 1 -i] = temp;
rotatedMap[`${i}-${j}`] = true;
rotatedMap[`${n - 1 - j}-${n - 1 - i}`] = true;
}
}
}
};Time Complexity:
O(n^2) since we visited all the cells in the matrix
Space Complexity:
O(1) since it’s in place