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

Each element moves uniquely according to one of four formulas, adding five movements of known sizes (I'll leave the size calculation out since you wanted to figure it out):

formula (one of these four):

left + down + right + up + left
down + right + up + left + down
right + up + left + down + right
up + left + down + right + up

Since the smallest side of the matrix is even, we know there is not an element remaining in place. After R rotations, the element has circled around floor (R / formula) times but still needs to undergo extra = R % formula shifts. Once you know extra, simply calculate the appropriate placement for the element.

Answer 2

I would start with a simplifying assumption: M is less than or equal to N. Thus, you are guaranteed to have an even number of rows. (What if M > N? Then transpose the matrix, carry out the algorithm, and transpose the matrix again.)

Because you have an even number of rows, you can easily find the corners of each cycle within the matrix. The outermost cycle has these corners:

a_1,1 → a_M,1 → a_M,N → a_1,N

To find the next cycle, move each corner inward, which means incrementing or decrementing the index at each corner as appropriate.

Knowing the sequence of corners allows you to iterate over each cycle and store the values in a one-dimensional vector. In each such vector a, start from index R % a.size() and increment the index a.size() - 1 times to iterate over the rotated elements of the cycle. Copy each element a[i % a.size()] back to the cycle.

Note that we don't actually rotate the vector. We accomplish the rotation by starting from an offset index when we copy elements back to the matrix. Thus, the overall running time of the algorithm is O(MN), which is optimal because it costs O(MN) just to read the input matrix.

Answer 3

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))

Answer 4

I would treat this as a problem that divides the matrix into submatrices. You could probably write a function that shifts the matrices (and submatrices) outer rows and columns by one each time you call it. Take care to handle the four corners of the matrix appropriately.

Check this out for suggestions how to shift the columns.

Edit (more detailed):

Read each matrix circle in as a vector, use std::rotate on it R % length.vector times, write back. Maximally 150 operations.