Rotate a 2D array in-place without using a new array - best C++ solution?

Question

One of my students asked me this kind of homework with C++ arrays. It seemed quite interesting for me, so, though I have solved this problem, I wanted to share my solution with you and know another variants and opinions. The problem is following:

Problem It is given a 2D dynamic quadratic matrix (array) A(nxn). It is required to rotate the array by 90 degree anticlockwise, that is to say, after rotation A[1,1] field should contain the value of A[1,n] and A[1,n] field should contain the value of A[n,n]. And also it is required that while solving this problem you should not use any other array.

My solution I have told to the student to do the following (will represent steps schematically):
I have suggested to define a class which, as its member, will have the 2D array. And to define a operation which will return reference on A[j,n+1-i] element when the user will request A[i,j] one. In two words I have suggested to create a wrapper for the array, and manipulate by array through the wrapper.

Answer 1

Below example is in Java and can be easily adopted to C++. Rotating large matrices in memory might consume a lot of resources especially when values of the matrix are complex objects. In such cases it might be more efficient to recalculate indexes with functions that would redirect them to elements of rotated matrix without actual rotation.

public class RotateArray {

public static char arr[][] = { { 'a', 'b', 'c','1' }, { 'd', 'e', 'f','2' }, { 'g', 'h', 'i','3' },{ 'j', 'k', 'l','4' } };
private static int imax = arr.length-1;
private static int jmax = arr[0].length-1;

public static void printArray() {

    for (int i = 0; i <= imax; i++) {
        for (int j = 0; j <= jmax; j++) {
            System.out.print(arr[i][j] + " ");
        }
        System.out.print("\n");
    }
}

public static void printRotatedArray() {
    for (int i = 0; i <= imax; i++) {
        for (int j = 0; j <= jmax; j++) {
            System.out.print(arr[getRotatedI(i,j)][getRotatedJ(i,j)] + " ");
        }
        System.out.print("\n");
    }
}   

public static int getRotatedI(int i,int j){     
    int ii = imax-j;
    return ii;
}

public static int getRotatedJ(int i,int j){
    int jj = i;
    return jj;
}       

public static void main(String[] args) {

    System.out.println("Printing matrix");
    printArray();
    System.out.println("Printing rotated matrix");
    printRotatedArray();
}

}

Output:

Printing matrix
a b c 1 
d e f 2 
g h i 3 
j k l 4 

Printing rotated matrix
j g d a 
k h e b 
l i f c 
4 3 2 1

Answer 2

O(n^2) time and O(1) space algorithm ( without any workarounds and hanky-panky stuff! )

Rotate by +90:

Transpose
Reverse each row

Rotate by -90:

Transpose
Reverse each column

Rotate by +180:

Method 1: Rotate by +90 twice

Method 2: Reverse each row and then reverse each column

Rotate by -180:

Method 1: Rotate by -90 twice

Method 2: Reverse each column and then reverse each row

Method 3: Reverse by +180 as they are same

Answer 3

Well, that is not C++ but Java. Sorry for this, but here is a recursive algorithm inside a simple array backed Matrix :

public void rotateInPlaceRecursive() {
    if( rowCount != colCount ) {
        throw new IllegalStateException("Matrix must be square");
    }
    doRotateInPlaceRecursive(0);
}

public void doRotateInPlaceRecursive(int shrink) {
    if( shrink == rowCount/2 ) {
        return;
    }
    for (int col = shrink; col < colCount-shrink-1; col++) {
        int row = shrink;
        int top     = tab[row][col];
        int left    = tab[rowCount-col-1][row];
        int bottom  = tab[rowCount-row-1][rowCount-col-1];
        int right   = tab[col][rowCount-row-1];

        tab[row][col] = right;
        tab[rowCount-col-1][row] = top;
        tab[rowCount-row-1][rowCount-col-1] = left;
        tab[col][rowCount-row-1] = bottom;

    }
    doRotateInPlaceRecursive(shrink+1);
}

---- TEST

@Test
public void testRotateInPlaceRecursive() {
    // given
    int N = 5;
    Matrix matrix = new Matrix(N, N);

    // when
    int i=0;
    for( int row = 0; row< N; row++ ) {
        for( int col = 0; col< N; col++ ) {
            matrix.set(row,col, i++ );
        }
    }

    // then
    matrix.rotateInPlaceRecursive();
    i = 0;
    for( int row = 0; row< N; row++ ) {
        for( int col = 0; col< N; col++ ) {
            assertEquals(i++,matrix.get(N-col-1,row));
        }
    }
}

Answer 4

You can use a "four-way-swap" and a nested loop with some rotation magic (worked out on paper):

template <typename T>
void swap(T& a, T& b, T& c, T& d)
{
    T x(a);
    a = b;
    b = c;
    c = d;
    d = x;
}

template <typename T, size_t dim>
void rotate(T (&matrix)[dim][dim])
{
    const size_t d = dim-1;
    for (size_t y = 0; y < dim/2; ++y)
    {
        for (size_t x = y; x < d-y; ++x)
        {
            swap(matrix[y  ][x  ],
                 matrix[x  ][d-y],
                 matrix[d-y][d-x],
                 matrix[d-x][y  ]);
        }
    }
}

Test program:

template <typename T, size_t dim>
void print(T (&matrix)[dim][dim])
{
    for (size_t y = 0; y < dim; ++y)
    {
        for (size_t x = 0; x < dim; ++x)
        {
            std::cout << matrix[y][x] << ' ';
        }
        std::cout << '\n';
    }
}

int main()
{
    int matrix[4][4] = {{1, 2, 3, 4},
                        {5, 6, 7, 8},
                        {9, 10, 11, 12},
                        {13, 14, 15, 16}};
    rotate(matrix);
    print(matrix);
}

Output:

4 8 12 16
3 7 11 15
2 6 10 14
1 5 9 13

Now you just have to convert that from template-form to dynamic-form ;)

Answer 5

Wikipedia has an article on in-place matrix transposition.

Consider:

a b c
e f g
x y z

transpose:
a e x
b f y
c g z

rotated 90 deg CCW:
c g z
b f y
a e x

So after you have the transpose, reverse the rows, which you can do in-place easily.