The “Rotate Image” problem is a common algorithmic challenge that tests your understanding of 2D arrays and in-place manipulation techniques. This problem is particularly relevant in interviews, as it demonstrates your ability to think critically about matrix transformations.
Problem Statement
You are given an (n \times n) 2D matrix representing an image. Your task is to rotate the image by 90 degrees clockwise.
Follow-up
Can you achieve this rotation in-place, without using additional space for another matrix?
Example:
- Input:
[
[1, 2, 3],
[4, 5, 6],
[7, 8, 9]
]
- Output:
[
[7, 4, 1],
[8, 5, 2],
[9, 6, 3]
]
Java Solution
public class RotateImage {
public void rotate(int[][] matrix) {
int n = matrix.length;
// Step 1: Transpose the matrix
for (int i = 0; i < n; i++) {
for (int j = i; j < n; j++) {
int temp = matrix[i][j];
matrix[i][j] = matrix[j][i];
matrix[j][i] = temp;
}
}
// Step 2: Reverse each row
for (int i = 0; i < n; i++) {
for (int j = 0; j < n / 2; j++) {
int temp = matrix[i][j];
matrix[i][j] = matrix[i][n - 1 - j];
matrix[i][n - 1 - j] = temp;
}
}
}
public static void main(String[] args) {
RotateImage solution = new RotateImage();
int[][] matrix = {
{1, 2, 3},
{4, 5, 6},
{7, 8, 9}
};
solution.rotate(matrix);
System.out.println("Rotated image:");
for (int[] row : matrix) {
for (int value : row) {
System.out.print(value + " ");
}
System.out.println();
}
}
}
Code Breakdown
- Class Declaration
public class RotateImage {
This line declares a public class named RotateImage.
- rotate Method
public void rotate(int[][] matrix) {
This method takes a 2D array (matrix) as input and modifies it to rotate the image in place.
- Matrix Size
int n = matrix.length;
The size of the matrix is stored in variable n.
- Transpose the Matrix
for (int i = 0; i < n; i++) {
for (int j = i; j < n; j++) {
int temp = matrix[i][j];
matrix[i][j] = matrix[j][i];
matrix[j][i] = temp;
}
}
This nested loop transposes the matrix, switching rows with columns.
- Reverse Each Row
for (int i = 0; i < n; i++) {
for (int j = 0; j < n / 2; j++) {
int temp = matrix[i][j];
matrix[i][j] = matrix[i][n - 1 - j];
matrix[i][n - 1 - j] = temp;
}
}
This nested loop reverses each row of the transposed matrix, completing the 90-degree clockwise rotation.
- Main Method
public static void main(String[] args) {
RotateImage solution = new RotateImage();
int[][] matrix = {
{1, 2, 3},
{4, 5, 6},
{7, 8, 9}
};
solution.rotate(matrix);
...
}
This is the entry point of the program, where the rotate method is called and the rotated matrix is printed.
Time and Space Complexity
- Time Complexity: (O(n^2))
The algorithm goes through the matrix twice: once for transposing and once for reversing the rows. - Space Complexity: (O(1))
The rotation is performed in place, requiring no additional storage beyond a few variables.
Example Output
For the given input:
Input:
[
[1, 2, 3],
[4, 5, 6],
[7, 8, 9]
]
Output: Rotated image:
[7, 4, 1]
[8, 5, 2]
[9, 6, 3]
This output confirms that the image has been successfully rotated by 90 degrees clockwise.
Conclusion
The “Rotate Image” problem is a great exercise in matrix manipulation techniques. Mastering this problem can enhance your problem-solving skills and prepare you for similar challenges in coding interviews.
For any questions or modifications, feel free to reach out to Divi Tech HR Solutions at info@divisolutions.in.
If you found this blog helpful, please leave a comment and like the post!
0 Comments