CODEWITHSUNDEEP
cmatrix
Andrew Laughlin
Andrew Laughlin

Reputation: 2022

In-place matrix rotation

An interesting question I found, asked that an NxN matrix be rotated, in-place by 90 degrees. My recursive solution, in C, is below. However when I looked up other solutions, most used a nested for loop to accomplish the task (which seems to work fine). The nested loop implementations appear to run in O(n^2) time.

See: How do you rotate a two dimensional array?

I believe the recursive solution runs in O( (n^2-n)/2 ), which is O(n^2) as well. My question is two-fold. 1) Is my complexity analysis above correct for both the recursive and non-recursive solutions, and 2) Is there some highly efficient or clever way to rotate a matrix that I haven't found?

TIA.

#include <stdio.h>
#include <stdlib.h>


int SIZE = 0;


/**
 * In-place, recursive, clockwise, 90 degree matrix rotation.
 */
static void rotate_in_place( int matrix[][SIZE], int n )
{
    if( n < 2 )
        return;


    int temp1, temp2;

    for( int i = 0; i < (n-1); i++ )
    {
        temp1 = matrix[i][n-1];
        matrix[i][n-1] = matrix[0][i];

        temp2 = matrix[n-1][n-i-1];
        matrix[n-1][n-i-1] = temp1;

        temp1 = matrix[n-i-1][0];
        matrix[n-i-1][0] = temp2;

        matrix[0][i] = temp1;
    }


    matrix = ((int*)matrix) + SIZE + 1;
    n -= 2;
    rotate_in_place( matrix, n );
}


static void print_matrix( int matrix[][SIZE] )
{
    printf( "\n" );
    for( int i = 0; i < SIZE; i++ )
    {
        for( int j = 0; j < SIZE; j++ )
            printf( "%4i ", matrix[i][j] );

        printf( "\n" );
    }
}


int main()
{

    // Create some matrices and rotate them.
    //
        int matrices = 10;

        for( int i = 2; i < matrices; i++ )
        {
            int matrix[i][i];

            int count = 0;
            for( int j = 0; j < i; j++ )
                for( int k = 0; k < i; k++ )
                    matrix[j][k] = ++count;


            printf( "\n\nRotating %ix%i matrix.\n", i, i );

            SIZE = i;

            printf( "\nOriginal matrix.\n" );
            print_matrix( matrix );

            rotate_in_place( matrix, i );

            printf( "\n\nRotated matrix.\n" );
            print_matrix( matrix );
        }


    return EXIT_SUCCESS;
}

Upvotes: 6

Views: 5995

Answers (3)

thiagoh
thiagoh

Reputation: 7388

in place C solution follows

void rotateRight(int matrix[][SIZE], int length) {

    int layer = 0;

    for (int layer = 0; layer < length / 2; ++layer) {

        int first = layer;
        int last = length - 1 - layer;

        for (int i = first; i < last; ++i) {

            int topline = matrix[first][i];
            int rightcol = matrix[i][last];
            int bottomline = matrix[last][length - layer - 1 - i];
            int leftcol = matrix[length - layer - 1 - i][first];

            matrix[first][i] = leftcol;
            matrix[i][last] = topline;
            matrix[last][length - layer - 1 - i] = rightcol;
            matrix[length - layer - 1 - i][first] = bottomline;
        }
    }
}

Upvotes: 3

Joel Falcou
Joel Falcou

Reputation: 6357

Rotation can't be done in less than n^2 operations as you are required to swap all element. Usually, however, as rotation trash the cache pretty hard, we avoid performing it ;)

Upvotes: 2

Fred Foo
Fred Foo

Reputation: 363567

Your complexity analysis is correct, but also very confusing. Since the number of elements in the matrix is n², O(n²) is effectively linear time in the size of the input, which is the figure that matters.

If you want to print the entire matrix after rotating it, then linear time is the best you can do. For other operations, it would be wiser not to rotate the matrix in-place but instead write an adapter that changes its indexing, so elements of the rotated matrix can be accessed without doing the actual rotation in memory.

Upvotes: 0

Related Questions