Rotate Image - LeetCode

#algorithms #tutorial #interview #leetcode

Problem Description

🔗 Link to Question: https://leetcode.com/problems/rotate-image/editorial/

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

Observation 🔎

Naive Approach

Observe that the ith col turns into ith row in reversed form
Create a New Matrix and use it to update the original matrix.

Code

class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        int n=matrix.size();
        auto v = matrix;

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

Complexity Analysis

Time: $O(n^2)$
Space: $O(n^2)$

Using Matrix Operations

Transpose the Matrix
- Now columns ↔ rows are interchanged Or we’ve performed a reverse operation around the diagonals.
Reverse the Rows.

We are just exploiting the fact that columns are turned into rows in reversed fashion.

Code

class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        int n=matrix.size();

        //Transpose the Matrix
        transpose(matrix);

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

    //Reverse around the Diagonal
    void transpose(vector<vector<int>>& matrix)
    {
        int n=matrix.size();
        for(int i=0; i<n; i++)
        {
            //[0..i-1] columns are correctly modified
            for(int j=i; j<n; j++)
            {
                swap(matrix[i][j], matrix[j][i]);
            }
            //After modifying ith row, ith col is also correctly modified
        }
    }
};