Rotate a 2D NxN matrix in Concentric Circles

Question

Given a 2D NxN matrix, visualize it as concentric circles. You have to find the rotated matrix where each element in the circle is rotated by 1 position layer by layer in an alternate clockwise and anticlockwise direction. All rotations should be in-place.

2 3 4 5
1 6 7 8
4 2 1 9
5 3 2 4

should get transformed to

1 2 3 4 
4 7 1 5 
5 6 2 8 
3 2 4 9 

I thought about the solution

1> For clockwise circle rotation, read elements in the order

i -> 0 to n-1 and j = 0
j -> 0 to n-1 and i = n-1
i -> n-1 to 0 and j = n-1
j -> n-1 to 0 and i = 0

2> For anti-clockwise circle rotation, read elements in the order

j -> 0 to n-1 and i = 0
i -> 0 to n-1 and j = n-1
j -> n-1 to 0 and i = n-1
i -> n-1 to 0 and j = 0

Code

for(int cnt = 0; cnt < n/2; cnt++)
    {   
        if(cnt%2 == 0) // Clockwise
        {   
            i = cnt; j = cnt;
            // while loops for each case
        }
        else // anti-clockwise
        {
            i = cnt; j = cnt;
            // while loops for each case
        }       
}

Is there any better approach to solve this problem in O(n2) or better ?

Answer 1

As your array is of size N*N and the desired computation demands each element to be visited atleast once, there cannot be a solution better than O(n^2) which uses 2 dimensional arrays.

I think that your solution will be fine if the operation has to be done single time on the same array.

If you have to do this operation multiple times on the same input array, better create circles from the input array. The data structure of circle should be a CLL (circular linked list). So doing the operation multiple times will be piece of cake as you have to change the root element of the CLL storing the circle info depending on the direction.