DEV Community

Cover image for DAY 5(II) - Rotate Image
Nayan Pahuja
Nayan Pahuja

Posted on • Edited on

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
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;

    }
Enter fullscreen mode Exit fullscreen mode

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.

Example

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());
        }


    }

Enter fullscreen mode Exit fullscreen mode

Complexity Analysis

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

Do your career a big favor. Join DEV. (The website you're on right now)

It takes one minute, it's free, and is worth it for your career.

Get started

Community matters

Top comments (0)

👋 Kindness is contagious

Discover a treasure trove of wisdom within this insightful piece, highly respected in the nurturing DEV Community enviroment. Developers, whether novice or expert, are encouraged to participate and add to our shared knowledge basin.

A simple "thank you" can illuminate someone's day. Express your appreciation in the comments section!

On DEV, sharing ideas smoothens our journey and strengthens our community ties. Learn something useful? Offering a quick thanks to the author is deeply appreciated.

Okay