18

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.

Improve this question
5
  • 3
    Your solution doesn't actually solve the problem. You're just returning the correct element for each query, but you're not actually rotating it like the problem asks you to. +1 for an interesting problem though. Commented Jun 29, 2010 at 13:01
  • 1
    @IVlad: actually, solving stays a matter of view. You can be quite certain that's how programs like matlab implement matrix transpose, just using a state and appropriate getters, no real transformations. Of course, I doubt my teachers would accept this answer on an exam :D. Commented Jun 29, 2010 at 13:14
  • Atention!!! All those solution use a new array! Solution should be without using a new array. Commented Jun 29, 2010 at 13:19
  • 1
    @nikhil No need to be pity! :) I have told them the right solution, OF COURSE! You may be pity for the students, whose teacher suggested a workaround and passed that problem, without returning to it with a better solution ;) Commented Sep 18, 2012 at 9:53
  • I do appreciate the fact that you did look for a better solution, also I had no intention to cause any personal hurt. Will delete my comment. Sorry about that. Commented Sep 18, 2012 at 12:22

5 Answers 5

Reset to default
22

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.

Improve this answer
Sign up to request clarification or add additional context in comments.

3 Comments

Wait, that is what I wrote! But since this is clearer, I will just delete mine. And +1 :-)
@Moron: I often have the problem myself, I am slow I guess :D
@Matthieu: :-) My guess is the way stackoverflow is implemented (caching and all). So even though I had posted 2-3 min before this one, perhaps it wasn't visible to others at the same time. In any case, I had a very terse answer and this one is a lot better in explaining why the method works.
5

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

Improve this answer

1 Comment

A recursive algorithm could be even more elegant and concise.
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));
        }
    }
}
Improve this answer

Comments

2

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
Improve this answer

Comments

-1

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

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.