Java: Rotate Image

Thought Process

The problem requires rotating an n x n matrix by 90 degrees clockwise. We achieve this in two steps: First, we transpose the matrix, which swaps elements across the diagonal. Second, we reverse each row of the transposed matrix to complete the rotation. This approach ensures the rotation is done in-place without using extra space. For rotating 90 degrees counter-clockwise, we would reverse the rows first and then transpose the matrix. 

class Solution {

    public void rotate(int[][] matrix) {
        
        // First transform the matrix
        for(int i=0;i<matrix.length;i++){
            for(int j=0;j<matrix[0].length;j++){

                if(i>j){
                    int tmp = matrix[i][j];
                    matrix[i][j] = matrix[j][i];
                    matrix[j][i] = tmp;
                }
            }
        }
        // Now, reverse the matrix, row wise.
        for(int i=0;i<matrix.length;i++){

            int left = 0;
            int right = matrix[0].length-1;

            while(left<right){
                int tmp = matrix[i][left];
                matrix[i][left] = matrix[i][right];
                matrix[i][right] = tmp;

                left++;
                right--;
            }
        }
        // Note: For rotating ACW, first reverse & then transform it.
    }
}

Code Complexity

Time Complexity: O(n2)

The algorithm iterates through each element of the matrix once, resulting in a time complexity of O(n2), where n is the number of rows/columns in the matrix.

Space Complexity: O(1)

The algorithm performs the rotation in-place, using only a constant amount of extra space.

Code copied!