Rotate Image LeetCode Solution

Problem Statement

Rotate Image LeetCode Solution – 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

Test Case 1:

Input: matrix = [[1,2,3],[4,5,6],[7,8,9]]

Output: [[7,4,1],[8,5,2],[9,6,3]]

Explanation

After rotating the matrix by 90 degrees, it becomes as shown in the figure.

Approach:

Idea:

So basically we need to reverse the matrix upside down first, and then swap each symmetric element.

1. Reverse each row in a for-loop. (No need to consider whether the number of rows is odd or even. “/” would naturally do the trick.)
2. We divide the matrix into three parts, that is to say, a diagonal (left top to right bottom), right up, left down.
3. We do not need to rotate the diagonal.
4. Now we only need to consider one of the two parts left. In this code, we swap each pair of symmetric elements in the right-up part.

Code for Rotate Image

Java Program

class Solution {
    public void rotate(int[][] matrix) {
        int length = matrix.length;
        for (int i = 0; i < length / 2; i++) {
            int[] temp = matrix[i];
            matrix[i] = matrix[length - i - 1];
            matrix[length - i - 1] = temp;
        }

        for (int i = 0; i < length - 1; i++) {
            for (int j = i + 1; j < length; j++) {
                int temp = matrix[i][j];
                matrix[i][j] = matrix[j][i];
                matrix[j][i] = temp;
            }
        }
    }
}

C++ Program

class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
      int n=matrix.size();
   
       for(int i=0;i<n;i++)
           for(int j=0;j<i;j++)
               swap(matrix[i][j],matrix[j][i]);

        for(int i=0;i<n;i++)
            reverse(matrix[i].begin(),matrix[i].end());
    }
};

Complexity Analysis for Rotate Image LeetCode Solution

Let M be the number of cells in the matrix.

• Time complexity: as each cell is getting read once and written once.
• Space complexity: $\mathcal{O}(1)$ because we do not use any other additional data structures.