Problem Statement
You are given a 2D matrix (n x n) representing an image or matrix. Rotate the matrix by 90 degrees (clockwise). You have to rotate the image or matrix in place, which means you have to modify the input matrix directly. Do not allocate another matrix and do the rotation.
Optimal Solution for rotation by 90 Degree
The optimal solution to rotating a matrix by 90 degrees is to use the following algorithm:
- Reverse the rows of the matrix.
- Transpose the matrix.
Reversing rows and transposing a matrix are both relatively simple operations, achievable in a single pass through the matrix. This makes the optimal solution to rotating a matrix by 90 degrees very efficient.
Java Implementation for rotation by 90 degrees
import java.util.Arrays; public class OptimalMatrixRotation { public static void rotateMatrixClockwise(int[][] matrix) { int n = matrix.length; // Reverse the rows 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; } } // Transpose the matrix for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { int temp = matrix[i][j]; matrix[i][j] = matrix[j][i]; matrix[j][i] = temp; } } } public static void main(String[] args) { int[][] matrix = { {1, 2, 3}, {4, 5, 6}, {7, 8, 9} }; System.out.println("Original Matrix:"); for (int[] row : matrix) { System.out.println(Arrays.toString(row)); } rotateMatrixClockwise(matrix); System.out.println("Matrix after 90-degree clockwise rotation:"); for (int[] row : matrix) { System.out.println(Arrays.toString(row)); } } }
Time Complexity: O(N*N) + O(N*N). The first one, O(N*N), is for transposing the matrix, and the second one is for reversing the matrix.
Space Complexity: O(1).
Benefits of the Optimal Solution
The optimal solution for matrix rotation in Java programming offers several advantages:
- Efficiency: The combination of transpose and row reversal minimizes the number of operations, making it highly efficient for large matrices.
- In-Place: The rotation is performed in-place, meaning no additional memory is required, making it memory-efficient.
- Simplicity: The straightforward implementation allows for easy integration into various applications.
Conclusion
As a Java developer, adding this essential technique to your toolkit will empower you to tackle complex matrix rotation challenges with ease. Embrace the power of the optimal solution, which offers a time complexity of O(n^2), and grow your Java programming skills to new heights!
I hope this article has been helpful. Please feel free to leave a comment below if you have any questions or contact us.
Pingback: Solving the 4Sum Problem: Efficient Algorithms in Java with Time and Space Complexity - Engineer Voice