Rotate Image

Leet code Link - https://leetcode.com/problems/rotate-image/description/

Complexity - Medium

Description

You are given an n x n 2D matrix representing an image, rotate the image by 90 degrees (clockwise).

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:

Input: matrix = [1,2,3],[4,5,6],[7,8,9](/shilpathota/99-leetcode-solutions/wiki/1,2,3],[4,5,6],[7,8,9)
Output: [7,4,1],[8,5,2],[9,6,3](/shilpathota/99-leetcode-solutions/wiki/7,4,1],[8,5,2],[9,6,3)

Example 2:

Input: matrix = [5,1,9,11],[2,4,8,10],[13,3,6,7],[15,14,12,16](/shilpathota/99-leetcode-solutions/wiki/5,1,9,11],[2,4,8,10],[13,3,6,7],[15,14,12,16)
Output: [15,13,2,5],[14,3,4,1],[12,6,8,9],[16,7,10,11](/shilpathota/99-leetcode-solutions/wiki/15,13,2,5],[14,3,4,1],[12,6,8,9],[16,7,10,11)

Constraints:

n == matrix.length == matrix[i].length
1 <= n <= 20
-1000 <= matrix[i][j] <= 1000

Solution

The most elegant solution for rotating the matrix is to first reverse the matrix around the main diagonal, and then reverse it from left to right. These operations are called transpose and reflect in linear algebra.

class Solution {
    public void rotate(int[][] matrix) {
        transpose(matrix);
        reflect(matrix);
    }
    public void transpose(int[][] matrix){
        int n=matrix.length; int m = matrix[0].length;
        for(int i=0;i<n;i++){
            for(int j=i+1;j<m;j++){
                int tmp = matrix[i][j];
                matrix[i][j]=matrix[j][i];
                matrix[j][i] = tmp;
            }
        }
    }

    public void reflect(int[][] matrix){
        int n=matrix.length; int m = matrix[0].length;
        for(int i=0;i<n;i++){
            for(int j=0;j<n/2;j++){
                int tmp = matrix[i][j];
                matrix[i][j]=matrix[i][n-1-j];
                matrix[i][n-1-j] = tmp;
            }
        }
    }
}

Let M be the number of cells in the grid.

Time complexity: O(M). We perform two steps; transposing the matrix, and then reversing each row. Transposing the matrix has a cost of O(M) because we're moving the value of each cell once. Reversing each row also has a cost of O(M), because again we're moving the value of each cell once.

Space complexity: O(1) because we do not use any other additional data structures.