DEV Community

Kathan Vakharia
Kathan Vakharia

Posted on

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 🔎

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)