Rotate a matrix n times

Question

I was solving problems on HackerRank when I got stuck at this one.

Problem Statement

You are given a 2D matrix, a, of dimension MxN and a positive integer R. You have to rotate the matrix R times and print the resultant matrix. Rotation should be in anti-clockwise direction.

Rotation of a 4x5 matrix is represented by the following figure. Note that in one rotation, you have to shift elements by one step only (refer sample tests for more clarity).

It is guaranteed that the minimum of M and N will be even.

Input

First line contains three space separated integers, M, N and R, where M is the number of rows, N is number of columns in matrix, and R is the number of times the matrix has to be rotated. Then M lines follow, where each line contains N space separated positive integers. These M lines represent the matrix.

Output

Print the rotated matrix.

Constraints

2 <= M, N <= 300 
1 <= R <= 10^9 
min(M, N) % 2 == 0 
1 <= aij <= 108, where i ∈ [1..M] & j ∈ [1..N]'

What I tried to do was store the circles in a 1D array. Something like this.

 while(true)
    {
        k = 0;
        for(int j = left; j <= right; ++j) {temp[k] = a[top][j]; ++k;}
        top++;
        if(top > down || left > right) break;

        for(int i = top; i <= down; ++i) {temp[k] = a[i][right]; ++k;}
        right--;
        if(top > down || left > right) break;

        for(int j = right; j >= left; --j) {temp[k] = a[down][j] ; ++k;}
        down--;
        if(top > down || left > right) break;

        for(int i = down; i >= top; --i) {temp[k] = a[i][left]; ++k;}
        left++;
        if(top > down || left > right) break;
    }

Then I could easily rotate the 1D matrix by calculating its length modulo R. But then how do I put it back in matrix form? Using a loop again would possibly cause a timeout.

Please don't provide code, but only give suggestions. I want to do it myself.

Solution Created :

#include <iostream>
using namespace std;



int main() {
int m,n,r;
cin>>m>>n>>r;
int a[300][300];
for(int i = 0 ; i < m ; ++i){
    for(int j = 0; j < n ; ++j)
        cin>>a[i][j];
}

int left = 0;
int right = n-1;
int top = 0;
int down = m-1;
int tleft = 0;
int tright = n-1;
int ttop = 0;
int tdown = m-1;
int b[300][300];
int k,size;
int temp[1200];

while(true){
    k=0;
    for(int i = left; i <= right ; ++i)
    {
        temp[k] = a[top][i];
      //  cout<<temp[k]<<" ";
        ++k;
    }
    ++top;

    if(top > down || left > right) 
        break;

    for(int i = top; i <= down ; ++i)
    {
        temp[k]=a[i][right];
       // cout<<temp[k]<<" ";
        ++k;
    }
    --right;
    if(top > down || left > right) 
        break;

    for(int i = right; i >= left ; --i)
    {
        temp[k] = a[down][i];
      //  cout<<temp[k]<<" ";
        ++k;
    }
    --down;

    if(top > down || left > right) 
        break;

    for(int i = down; i >= top ; --i)
    {   
        temp[k] = a[i][left];
       // cout<<temp[k]<<" ";
        ++k;
    }

    ++left;
    if(top > down || left > right) 
        break;

    //________________________________\\

    size = k;
    k=0;
   // cout<<size<<endl;
    for(int i = tleft; i <= tright ; ++i)
    {
        b[ttop][i] = temp[(k + (r%size))%size];
     //   cout<<(k + (r%size))%size<<" ";
     //   int index = (k + (r%size))%size;
       // cout<<index;
        ++k;
    }
    ++ttop;

    for(int i = ttop; i <= tdown ; ++i)
    {
        b[i][tright]=temp[(k + (r%size))%size];
        ++k;
    }
    --tright;

    for(int i = tright; i >= tleft ; --i)
    {
        b[tdown][i] = temp[(k + (r%size))%size];
        ++k;
    }
    --tdown;

    for(int i = tdown; i >= ttop ; --i)
    {   
        b[i][tleft] = temp[(k + (r%size))%size];
        ++k;
    }

    ++tleft;
}

size=k;
k=0;
if(top != ttop){
    for(int i = tleft; i <= tright ; ++i)
    {
        b[ttop][i] = temp[(k + (r%size))%size];
        ++k;
    }
    ++ttop;
}
if(right!=tright){
    for(int i = ttop; i <= tdown ; ++i)
    {
        b[i][tright]=temp[(k + (r%size))%size];
        ++k;
    }
    --tright;
}
if(down!=tdown){
    for(int i = tright; i >= tleft ; --i)
    {
        b[tdown][i] = temp[(k + (r%size))%size];
        ++k;
    }
    --tdown;
}
if(left!=tleft){
    for(int i = tdown; i >= ttop ; --i)
    {   
        b[i][tleft] = temp[(k + (r%size))%size];
        ++k;
    }

    ++tleft;
}
for(int i = 0 ; i < m ;++i){
    for(int j = 0 ; j < n ;++j)
        cout<<b[i][j]<<" ";
    cout<<endl;
}

return 0;
}

Answer 1

You need to break down this problem (remind me of an interview question from gg and fb) :

1. Solve first rotating a sequence one a single position
2. Then solve rotating a sequence N times
3. Model each "circle" or ring as an array. You may or may not actually need to store in a separate data
4. Iterate over each ring and apply the rotating algorithm

Lets consider the case of an array of length L which needs to be rotated R time. Observe that if R is a multiple of L, the array will be unchanged. Observe too that rotating x times to the right is the same as rotating L - x to the left (and vice versa).

1. Thus you can first design an algorithm able to rotate once either left or right one exactly one position
2. Reduce the problem of rotating R times to the left to rotating R modulo L to the left
3. If you want to go further reduce the problem of rotating R modulo L to the left to rotating left R modulo L or rotating right L - R modulo L. Which means if you have 100 elements and you have to do 99 rotations left, you better do 1 rotation right and be done with it.

So the complexity will be O ( Number of circles x Circle Length x Single Rotation Cost)

With an array in-place it means O( min(N,m) * (N * M)^2 )

If you use a doubly linked list as temporary storage, a single rotation sequence is done by removing the front and putting it at the tail (or vice versa to rotate right). So what you can do is copy all data first to a linked list. Run the single rotation algorithm R modulo L times, copy back the linked list on the ring position, and move on the next right till all rings are processed.

• Copy ring data to list is O(L), L <= N*M
• Single Rotation Cost is O(1)
• All rotations R modulo L is O(L)
• Repeat on all min(N,m) rings

With a spare double linked list it means complexity of O( min(N,m) * (N * M))