2
LeetCode - Rotate Image
source link: https://dev.to/_alkesh26/leetcode-rotate-image-2b2o
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
Problem statement
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.
Problem statement taken from: https://leetcode.com/problems/rotate-image
Example 1:
Input: matrix = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
Output: [[7, 4, 1], [8, 5, 2], [9, 6, 3]]
Enter fullscreen modeExit fullscreen mode
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]]
Enter fullscreen modeExit fullscreen mode
Example 3:
Input: matrix = [[1]]
Output: [[1]]
Enter fullscreen modeExit fullscreen mode
Example 4:
Input: matrix = [[1, 2], [3, 4]]
Output: [[3, 1], [4, 2]]
Enter fullscreen modeExit fullscreen mode
Constraints:
- matrix.length == n
- matrix[i].length == n
- 1 <= n <= 20
- -1000 <= matrix[i][j] <= 1000
Enter fullscreen modeExit fullscreen mode
Explanation
Rotate Groups of Four Cells
The first solution we can think of is to rotate
the four corners of the matrix.
We repeat this of the subsequent cells too.
Let's check the algorithm.
- initialize m = matrix.size, tmp
- loop for i = 0; i < m / 2; i++
- loop for j = i; j < m - 1 - i; j++
- tmp = matrix[i][j]
- matrix[i][j] = matrix[m - 1 - j][i]
- matrix[m - 1 - j][i] = matrix[m - 1 - i][m - 1 - j]
- matrix[m - 1 - i][m - 1 - j] = matrix[j][m - 1 - i]
- matrix[j][m - 1 - i] = tmp
Enter fullscreen modeExit fullscreen mode
The time complexity of the program is O(M) as each cell is getting read once and written once.
Space complexity is O(1) because we do not use any other additional data structures.
C++ solution
class Solution {
public:
void rotate(vector<vector<int>>& matrix) {
int m = matrix.size(), tmp;
int j = 0;
for(int i = 0; i < m/2; i++){
for(int j = i; j < m - 1 - i; j++){
tmp = matrix[i][j];
matrix[i][j] = matrix[m - 1 - j][i];
matrix[m - 1 - j][i] = matrix[m - 1 - i][m - 1 - j];
matrix[m - 1 - i][m - 1 - j] = matrix[j][m - 1 - i];
matrix[j][m - 1 - i] = tmp;
}
}
}
};
Enter fullscreen modeExit fullscreen mode
Golang solution
func rotate(matrix [][]int) {
m := len(matrix)
tmp := 0
for i := 0; i < m / 2; i++ {
for j := i; j < m - 1 - i; j++ {
tmp = matrix[i][j];
matrix[i][j] = matrix[m - 1 - j][i];
matrix[m - 1 - j][i] = matrix[m - 1 - i][m - 1 - j];
matrix[m - 1 - i][m - 1 - j] = matrix[j][m - 1 - i];
matrix[j][m - 1 - i] = tmp;
}
}
}
Enter fullscreen modeExit fullscreen mode
Javascript solution
var rotate = function(matrix) {
let m = matrix.length;
let tmp = 0;
let i, j;
for(i = 0; i < m/2; i++){
for(j = i; j < m - 1 - i; j++){
tmp = matrix[i][j];
matrix[i][j] = matrix[m - 1 - j][i];
matrix[m - 1 - j][i] = matrix[m - 1 - i][m - 1 - j];
matrix[m - 1 - i][m - 1 - j] = matrix[j][m - 1 - i];
matrix[j][m - 1 - i] = tmp;
}
}
};
Enter fullscreen modeExit fullscreen mode
Let's dry-run our algorithm to see how the solution works.
Input:
matrix = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
Step 1: m = matrix.length
m = 3
Step 2: tmp = 0
Step 3: loop i = 0; i < 3/2
0 < 3/2
0 < 1
true
j = i; j < 3 - 1 - 0
0 < 2
true
tmp = matrix[i][j]
tmp = 1
matrix[i][j] = matrix[m - 1 - j][i]
matrix[0][0] = matrix[3 - 1 - 0][0]
matrix[0][0] = matrix[2][0]
matrix[0][0] = 7
matrix[m - 1 - j][i] = matrix[m - 1 - i][m - 1 - j]
matrix[3 - 1 - 0][0] = matrix[3 - 1 - 0][3 - 1 - 0]
matrix[2][0] = matrix[2][2]
matrix[2][0] = 9
matrix[m - 1 - i][m - 1 - j] = matrix[j][m - 1 - i]
matrix[3 - 1 - 0][3 - 1 - 0] = matrix[0][3 - 1 - 0]
matrix[2][2] = matrix[0][2]
matrix[2][2] = 3
matrix[j][m - 1 - i] = tmp
matrix[0][3 - 1 - 0] = 1
matrix[0][2] = 1
j++
j = 1
Step 4: j < 2
1 < 2
true
tmp = matrix[0][1]
tmp = 2
matrix[i][1] = matrix[m - 1 - j][i]
matrix[0][1] = matrix[3 - 1 - 1][0]
matrix[0][1] = matrix[1][0]
matrix[0][1] = 4
matrix[m - 1 - j][i] = matrix[m - 1 - i][m - 1 - 1]
matrix[3 - 1 - 1][0] = matrix[3 - 1 - 0][3 - 1 - 1]
matrix[1][0] = matrix[2][1]
matrix[1][0] = 8
matrix[m - 1 - i][m - 1 - j] = matrix[j][m - 1 - i]
matrix[3 - 1 - 0][3 - 1 - 1] = matrix[1][3 - 1 - 0]
matrix[2][1] = matrix[1][2]
matrix[2][1] = 6
matrix[1][m - 1 - i] = tmp
matrix[1][3 - 1 - 0] = 1
matrix[1][2] = 2
j++
j = 2
Step 5: j < 2
2 < 2
false
Step 6: i++
i = 1
1 < 3/2
1 < 1
false
Output:
[[7, 4, 1], [8, 5, 2], [9, 6, 3]]
Enter fullscreen modeExit fullscreen mode
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK