ROTATE MATRIX PROGRAM IN JAVA

Given an image represented by an N*N . Write a method to rotate the image by 90 degrees.

public class RotateMatrix {

    public void rotate(int[][] matrix) {
        int n = matrix.length;
        for (int layer = 0; layer < n / 2; layer++) {
            int first = layer;
            int last = n - 1 - layer;
            for (int i = first; i < last; i++) {
                int offset = i - first;
                int top = matrix[first][i]; // save top

                // left->top
                matrix[first][i] = matrix[last - offset][first];

                // bottom->left
                matrix[last - offset][first] = matrix[last][last - offset];

                // right->bottom
                matrix[last][last - offset] = matrix[i][last];

                // top->right
                matrix[i][last] = top;
            }
        }
    }

    public void printMatrix(int[][] matrix) {
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[i].length; j++) {
                System.out.print(matrix[i][j] + " ");
            }
            System.out.println();
        }
    }

    public static void main(String[] args) {
        RotateMatrix rotateMatrix = new RotateMatrix();

        int[][] matrix = {
                {1, 2, 3},
                {4, 5, 6},
                {7, 8, 9}
        };

        System.out.println("Original Matrix:");
        rotateMatrix.printMatrix(matrix);

        rotateMatrix.rotate(matrix);

        System.out.println("Rotated Matrix:");
        rotateMatrix.printMatrix(matrix);
    }
}

Let’s go through the program step by step:

1. The rotate method takes a 2D integer array matrix as input and rotates it 90 degrees clockwise.
2. It starts by getting the length of the matrix n, which is assumed to be a square matrix (same number of rows and columns).
3. The outer loop iterates through each “layer” of the matrix. For an N x N matrix, there are N/2 such layers because we only need to rotate the outermost layers to rotate the entire matrix.
4. For each layer, the program defines two variables, first and last, which represent the indices of the first and last elements in the current layer.
5. The inner loop then iterates through each element in the current layer, starting from first and ending at last - 1.
6. For each element, the program calculates the offset, which is the difference between the current index i and first. This offset is used to determine the corresponding elements to swap for the rotation.
7. The program then performs a series of swaps to rotate the elements:
   • It saves the value of the top element (matrix[first][i]) in a variable top.
   • It then moves the value from the bottom of the layer (matrix[last - offset][first]) to the top (matrix[first][i]).
   • Next, it moves the value from the right of the layer (matrix[last][last - offset]) to the bottom.
   • Then, it moves the value from the left of the layer (matrix[i][last]) to the right.
   • Finally, it moves the saved top value to the left, completing the rotation for that element.
8. After rotating all elements in the current layer, the outer loop moves to the next layer, and the process repeats until all layers have been rotated.

This approach achieves the 90-degree clockwise rotation in place, meaning it modifies the original matrix without using additional space proportional to the input matrix size. The time complexity of this approach is O(N^2), where N is the number of elements in the matrix, as we iterate through each element once. The space complexity is O(1), as we only use a few extra variables regardless of the size of the input matrix.