Rotate Image

Companies:
  • Amazon Interview Questions
  • Apple Interview Questions
  • Cisco Interview Questions
  • Facebook Interview Questions
  • Microsoft Interview Questions

Problem Statement

You are given an n x n 2D matrix representing an image.

Rotate the image by 90 degrees (clockwise).

Note:

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.

Sample Test Cases

Given <strong>input matrix</strong> = 
[
  [1,2,3],
  [4,5,6],
  [7,8,9]
],

rotate the input matrix <strong>in-place</strong> such that it becomes:
[
  [7,4,1],
  [8,5,2],
  [9,6,3]
]
Given input matrix =
[
  [ 5, 1, 9,11],
  [ 2, 4, 8,10],
  [13, 3, 6, 7],
  [15,14,12,16]
], 

rotate the input matrix in-place such that it becomes:
[
  [15,13, 2, 5],
  [14, 3, 4, 1],
  [12, 6, 8, 9],
  [16, 7,10,11]
]

Problem Solution

We can solve this problem just by matrix manipulation.

Steps 1:

First we will do in-place transpose of the matrix ie we will be taking our row and turning them into our column.

this we can do by swapping the elements positioned at ( i, j ) with the elements at ( j, i ) as shown in the below gif.

Step 2:

In this step we will be horizontally flipping the columns.

In this we are actually following the Two-pointer algorithm ie, we will be having pointer at the beginning and end of each row that goes towards the middle and on the way we are swapping these elements until we reach the middle element ie, the element at (i, j) is swapped with the element (i, N-j-1) where N is the order of the matrix. (see the gif below)

Complexity Analysis

Time Complexity: O(n^2) we are traversing the entire matrix.

Space Complexity: O(1) we are making changes in the same matrix.

Code Implementation

#include<bits/stdc++.h>
using namespace std;

void print(vector< vector<int> > matrix)
{
   for(int i=0;i<matrix.size();i++)
    {   vector<int>temp;
        for(int j=0;j<matrix[0].size();j++)
        {
            cout<<matrix[i][j]<<" ";
        }
        cout<<endl;
    }
}

void rotate(vector< vector<int> > matrix) {
        int n=matrix.size();
     //  Step 1 Transpose Matrix (Turns Rows into Columns)
        for(int i=0;i<n;i++)
        {
            for(int j=i;j<n;j++)
            {
                swap(matrix[i][j],matrix[j][i]);
            }
        }

        // Swapping the columns till we reach the middle of the matrix.
        for(int i=0;i<matrix.size();i++)
        {
            for(int j=0;j<(int)matrix[i].size()/2;j++)
            {
                int temp=matrix[i][j];
                matrix[i][j]=matrix[i][n-1-j];
                matrix[i][n-1-j]=temp;
            }
        }
        print(matrix);

    }

int main()
{
    vector< vector<int> >matrix;
    int k=1;
    for(int i=0;i<3;i++)
    {   vector<int>temp;
        for(int j=0;j<3;j++)
        {
            temp.push_back(k++);
        }
        matrix.push_back(temp);
    }

    rotate(matrix);

}

 

Scroll to Top