DAY 5(II) - Rotate Image

Hello to anyone reading this. I am still relatively new to coding and this platform as well, so please feel free to drop any corrections/advice for me.
I am trying to do the 100 Day-Challenge of consistent coding and this is Day-5.Looking forward to a positive interaction with all of you.

DAY 5 Problem 2: Rotate Image

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:

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

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

Intuition:

We can closely observe the original matrix and the final matrix to deduce this out.
Starting the row from top, row of the matrix is in the ending column in resultant matrix.
To use this approach , we will have to take another matrix of n*n but that will exceed the required space complexity. But still let's take a look at it.

vector<vector<int>> rotate(vector<vector<int>>& matrix) {
        vector<vector<int>> matrixAns;
        int size = matrix.size();

        for(int i = 0; i < size; i++)
        {
            for(int j = 0; j < size; j++)
            {
                matrixAns[j][size-i-1] = matrix[i][j];
            }
        }
    return matrixAns;

    }

Complexity Analysis

Time Complexity: O(N^2)
Space Complexity: O(N)

Although this is an approach, in a space constrained environment. It will most likely fail.
So we are going to have to come up with a better approach.

Optimal Solution

• To solve this, We will have to know what a transpose of a matrix is.
• To put it simply a transpose of a matrix swaps the element of a matrix in diagonally opposite position
• That is , swapping of rows and columns
• After simply transposing, we will reverse elements in each row and get the desired answer.

void transposeMatrix(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]);
            }
        }
    }
    void rotate(vector<vector<int>>& matrix) {
        transposeMatrix(matrix);
        for(int i = 0; i < matrix.size(); i++)
        {
            reverse(matrix[i].begin(),matrix[i].end());
        }


    }

Complexity Analysis

Time Complexity: O(N^2)
Space Complexity: O(1)