CODEWITHSUNDEEP
c++arraysalgorithmmatrixrotation
user7634144
user7634144

Reputation: 31

Rotating an N x N matrix counterclockwise by 90 degrees. Why does order of filling in the values matter?

From GeeksforGeeks' "Inplace rotate square matrix by 90 degrees":

// An Inplace function to rotate a N x N matrix
// by 90 degrees in anti-clockwise direction
void rotateMatrix(int mat[][N])
{
    // Consider all squares one by one
    for (int x = 0; x < N / 2; x++)
    {
        // Consider elements in group of 4 in 
        // current square
        for (int y = x; y < N-x-1; y++)
        {
            // store current cell in temp variable
            int temp = mat[x][y];

            // move values from right to top
            mat[x][y] = mat[y][N-1-x];

            // move values from bottom to right
            mat[y][N-1-x] = mat[N-1-x][N-1-y];

            // move values from left to bottom
            mat[N-1-x][N-1-y] = mat[N-1-y][x];

            // assign temp to left
            mat[N-1-y][x] = temp;
        }
    }
}

For moving the values from left to bottom, why does filling in the values clockwise work:

m[N-1-x][N-1-y] = m[N-1-y][x];

It returns the correctly rotated matrix:

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

But filling in the values counterclockwise doesn't work:

m[N-1-x][y] = m[y][x];

It returns the incorrectly rotated matrix:

 4  8 12 16 
 3  7 11 15 
 2  6 11  5 
 1  5  2 16

I thought that it shouldn't matter which direction we fill in the values because the fields seem to be all going in the same place but in a different order. Why does it matter?

And intuitively it seems that we should fill in values counterclockwise, not clockwise, since we are rotating the N x N matrix by 90 degrees.

Upvotes: 3

Views: 2921

Answers (1)

samgak
samgak

Reputation: 24417

I thought that it shouldn't matter which direction we fill in the values because the fields seem to be all going in the same place but in a different order.

If you thought that, you are correct.

Why does it matter?

It doesn't matter. You can do it counterclockwise too:

int temp = mat[N-1-y][x];

mat[N-1-y][x] = mat[N-1-x][N-1-y];

mat[N-1-x][N-1-y] = mat[y][N-1-x];

mat[y][N-1-x] = mat[x][y];

mat[x][y] = temp;

and the matrix will be rotated clockwise. You just need to process the cells in the opposite order.

And intuitively it seems that we should fill in values counterclockwise, not clockwise, since we are rotating the N x N matrix by 90 degrees.

Suppose you have 4 pebbles in a row and you want to move them one position to the right. If you go from left to right, you will be moving each pebble into a position that is already occupied. So what you do is move from right to left, moving the rightmost one to the right first to make a space, then the next rightmost one into the position that was made vacant, and so on. So the order you process them is the opposite to the direction you are moving them. Same principle applies here, with the exception that we are using one temp variable to "wrap around" and create a cycle. It like we're putting the rightmost one to one side at the start, and then inserting it at the leftmost position when we're finished.

Upvotes: 1

Related Questions