Solution For Rotate Image
Problem Statement:
You are given an n x n 2D matrix representing an image, rotate the image by 90 degrees (clockwise).
You have to modify the input matrix in-place. Do not allocate another 2D matrix and do not return anything from your function.
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 = [[1]] Output: [[1]]
Approach:
In this problem, we need to rotate an image by 90 degrees. We can do this by swapping the elements in clockwise direction. We can swap the elements in the matrix in a nested loop.
We iterate over the first half of the matrix (i < n/2) and for each element, we swap it with the corresponding element in the clockwise direction. We do the swapping in four steps.
Let’s take an example of a 3 x 3 matrix:
Initial Matrix:
1 2 3
4 5 6
7 8 9
Step 1: Swap the elements as shown below:
7 2 1
4 5 6
9 8 3
Step 2: Swap the elements as shown below:
7 4 1
2 5 8
9 6 3
Step 3: Swap the elements as shown below:
7 4 1
8 5 2
9 6 3
This is the final rotated matrix.
Implementation:
Let’s take the example of a 3 x 3 matrix to explain the approach.
We have an input matrix of:
1 2 3
4 5 6
7 8 9
We need to swap the elements of this matrix to get the final matrix:
7 4 1
8 5 2
9 6 3
Step 1: Swap the elements
To do this, we need to use a nested loop to iterate over the first half of the matrix. We only need to iterate over the first half of the matrix because we are swapping the elements in place.
We can swap the elements using a temporary variable.
for (int i = 0; i < n/2; i++) {
for (int j = i; j < n-i-1; j++) {
int temp = matrix[i][j];
matrix[i][j] = matrix[n-j-1][i];
matrix[n-j-1][i] = matrix[n-i-1][n-j-1];
matrix[n-i-1][n-j-1] = matrix[j][n-i-1];
matrix[j][n-i-1] = temp;
}
}
Step 2: Print the rotated matrix
After swapping the elements, we can print the rotated matrix as follows:
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cout << matrix[i][j] << " ";
}
cout << endl;
}
This will print the following matrix:
7 4 1
8 5 2
9 6 3
The full implementation code for this problem is given below:
void rotate(vector
int n = matrix.size();
for (int i = 0; i < n/2; i++) {
for (int j = i; j < n-i-1; j++) {
int temp = matrix[i][j];
matrix[i][j] = matrix[n-j-1][i];
matrix[n-j-1][i] = matrix[n-i-1][n-j-1];
matrix[n-i-1][n-j-1] = matrix[j][n-i-1];
matrix[j][n-i-1] = temp;
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cout << matrix[i][j] << ” “;
}
cout << endl;
}
}
This implementation has a time complexity of O(n^2) because we need to swap n^2/2 elements. It also has a space complexity of O(1) because we are swapping the elements in place.
Step by Step Implementation For Rotate Image
class Solution { public void rotate(int[][] matrix) { // transpose matrix for (int i = 0; i < matrix.length; i++) { for (int j = i; j < matrix[0].length; j++) { int temp = matrix[i][j]; matrix[i][j] = matrix[j][i]; matrix[j][i] = temp; } } // reverse each row for (int i = 0; i < matrix.length; i++) { for (int j = 0; j < matrix[0].length / 2; j++) { int temp = matrix[i][j]; matrix[i][j] = matrix[i][matrix[0].length - 1 - j]; matrix[i][matrix[0].length - 1 - j] = temp; } } } }
Given an image represented by an NxN matrix, where each pixel in the image is 4 bytes, write a method to rotate the image by 90 degrees. Can you do this in place? def rotate_image(matrix): # transpose matrix for i in range(len(matrix)): for j in range(i, len(matrix)): matrix[j][i], matrix[i][j] = matrix[i][j], matrix[j][i] # reverse rows for row in matrix: row.reverse()
/** * @param {number[][]} matrix * @return {void} Do not return anything, modify matrix in-place instead. */ var rotate = function(matrix) { // transpose the matrix for (let i = 0; i < matrix.length; i++) { for (let j = i; j < matrix[0].length; j++) { let temp = matrix[i][j]; matrix[i][j] = matrix[j][i]; matrix[j][i] = temp; } } // reverse each row for (let i = 0; i < matrix.length; i++) { for (let j = 0; j < matrix[0].length / 2; j++) { let temp = matrix[i][j]; matrix[i][j] = matrix[i][matrix[0].length - 1 - j]; matrix[i][matrix[0].length - 1 - j] = temp; } } };
You are given an n x n 2D matrix representing an image. Rotate the image by 90 degrees (clockwise). Note: 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. Example 1: Given input matrix = [ [1,2,3], [4,5,6], [7,8,9] ], rotate the input matrix in-place such that it becomes: [ [7,4,1], [8,5,2], [9,6,3] ] Example 2: Given input matrix = [ [ 5, 1, 9,11], [ 2, 4, 8,10], [13, 3, 6, 7], [15,14,12,16] ], rotate the input matrix in-place such that it becomes: [ [15,13, 2, 5], [14, 3, 4, 1], [12, 6, 8, 9], [16, 7,10,11] ] // Solution: void rotate(vector>& matrix) { // We take transpose of the matrix for(int i = 0; i public class Solution { public void Rotate(int[][] matrix) { // edge case: if matrix is null or empty, return if (matrix == null || matrix.Length == 0) { return; } // transpose the matrix for (int i = 0; i < matrix.Length; i++) { for (int j = i; j < matrix[0].Length; j++) { int temp = matrix[i][j]; matrix[i][j] = matrix[j][i]; matrix[j][i] = temp; } } // reverse each row in the matrix for (int i = 0; i < matrix.Length; i++) { for (int j = 0; j < matrix[0].Length / 2; j++) { int temp = matrix[i][j]; matrix[i][j] = matrix[i][matrix[0].Length - 1 - j]; matrix[i][matrix[0].Length - 1 - j] = temp; } } } }