DEV Community

Kathan Vakharia
Kathan Vakharia

Posted on

Rotate Image - 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 🔎

Observe

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];
            }
        }
    }
};
Enter fullscreen mode Exit fullscreen mode

Complexity Analysis

  • Time: O(n2)O(n^2)
  • Space: O(n2)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
        }
    }
};
Enter fullscreen mode Exit fullscreen mode

Complexity Analysis

  • Time: O(n2)O(n^2)
  • Space: O(1)O(1)

Top comments (0)