Do not miss this exclusive book on Binary Tree Problems. Get it now for free.

In this article, we have explored an efficient way to Rotate Image: matrix of size NxN by 90 degrees (clockwise) inplace by using a property of XOR operation.

Table Contents

Introduction
Algorithm
Code in C++ and Implementation
Final considerations

Prerequisite: Bitwise operations, Applications of XOR operation

This is similar to Leetcode problem 48. Rotate Image.

1. Introduction

Rotation is part of Geometric Transformations, along with translation and scale.

translation is related to the element's position in the universe;
scale, defines the size of the object;
rotation, the orientation of the element.

When it comes to the matrix, rotation of the matrix is performed only in the quadratic matrices (the number of rows and columns are equal). The rotation direction can be counterclockwise or clockwise.

In the problem, we have to rotate a matrix of size NxN by 90 degrees (clockwise). We have to do this inplace that is modify the input matrix without using another matrix. This is the challenging part.

Input 3x3 image:

11	12	13
21	22	23
31	32	33

Output 90 degree rotated clockwise:

31	21	11
32	22	12
33	22	13

2. Algorithm

To rotate the elements contained within a matrix should be considered:

rotation occurs only on square matrices (number of rows and columns are equal);
each matrix element can vary in 4 positions (0, π, π/2, and 3π/2 ). After completing the cycle, the elements return to their original position.
To rotate the element:

a) subtract from the size of the matrix, the value of the column of the element;
b) after this procedure, the row of the column is inverted;

the order in which these arithmetic operations will define the direction of rotation of the matrix elements:

a) change row and column and then subtract = Clockwise.
b) subtract and then change the row and column = Counterclockwise.

In the code (Figure 5), to invert the elements of the matrices, the code contains the XOR (^) operator (Exclusive Or) and its property A ^ B ^ B = A.
The operation result is one (if the two input bits are different) and returns zero when the input bits are equal.

The XOR operator is often used to invert some of the bits of an integer expression.
In other words, in the mask of this operator, if there is one, the corresponding bit is inverted. If there is zero, the bit is kept as it is.

3. Code in C++ and Implementation

The article used a code in C++ (Figure 5), which rotates the elements of a matrix clockwise by 90 degrees.

Code development involved:

import iostream library;
creation of four for repetition loops, for receiving and organizing the elements and rotating them in 90 degrees;
a block to inform the matrix size;
a block for inserting the values of the matrix elements (inline entry);
command to print the result.

To better enter the steps described above, a test was performed with the code (Figure 5) using a 3x3 matrix (Figure 1):

11	12	13
21	22	23
31	32	33

Figura 1. Matrix before rotation.

Before informing the matrix values, it was necessary to indicate the matrix size. The code allows testing matrices of several sizes.
Input values have been laid out in three lines by code.

First row of the matrix: 11, 12, and 13;
Second row of the matrix: 21, 22, and 23;
Third row of the matrix: 31, 32, and 33.

The data reported were analyzed and organized in the first and second loop of the for. In this block, if the line is different from the column, the elements of the matrices are organized according to the XOR (^) operator (inversion of the matrix elements where i!=j) (Figure 2).

...
for(i=0; i<n; i++) {
    for(j=i; j<n; j++) {
        if(i!=j) {
            arr[i][j]^=arr[j][i];
            arr[j][i]^=arr[i][j];
            arr[i][j]^=arr[j][i];       
...

Figure 2. The first block, for the analysis and organization of data entered by the user.

After arranging the data in memory, the array in the second block containing the third and fourth ** for ** loops rotated the matrix elements 90 degrees clockwise (Figure 3).

In this block, the XOR operator inverted the elements and treated the values.
The line of code responsible for rotating the elements clockwise or counterclockwise is with an asterisk (*) in Figure 3.

The XOR operator in the blocks was necessary to compare two values individually ([i] and [j]) and produce a third result. At the end of the comparisons and rearrangements made with its use, the XOR operator returned the third result (matrix rotation).

...
for(i=0; i<n/2; i++) {
    for(j=0; j<n; j++) {
        arr[j][i]^=arr[j][n-1-i];
        arr[j][n-1-i]^=arr[j][i];*
        arr[j][i]^=arr[j][n-1-i];
...

Figure 3. The second block rotates 90 degrees clockwise the matrix.

The code will generate the rotated result without using extra memory. In other words, the receive and organization process memory is the same used for rotation.
The result obtained on screen was (Figure 4):

31	21	11
32	22	12
33	22	13

Figure 4. The output obtained for a 3x3 matrix.

Note that after rotation, the values of the first row (11, 12, and 13) (Figure 1), after rotates 90 degrees, the same values are in the third column (Figure 4).
Figure 5 is the complete code used to rotate the example (Figure 1) mentioned in this article.

#include <iostream>

using namespace std;

int n;
unsigned int arr[100][100];

void rotate() {
    int i,j;
    for(i=0; i<n; i++) {
        for(j=i; j<n; j++) {
            if(i!=j) {
                arr[i][j]^=arr[j][i];
                arr[j][i]^=arr[i][j];
                arr[i][j]^=arr[j][i];
            }
        }
    }

    for(i=0; i<n/2; i++) {
        for(j=0; j<n; j++) {
            arr[j][i]^=arr[j][n-1-i];
            arr[j][n-1-i]^=arr[j][i];
            arr[j][i]^=arr[j][n-1-i];
        }
    }
}
void display(){

    int i,j;

    for(i=0;i<n;i++) {
        for(j=0;j<n;j++) {
            cout<<arr[i][j]<<" ";
            }
            cout<<endl;
        }
    }

    int main(int argc, char *argv[]){

    int i,j;

    cout<< "Matrix Size: "<<endl;
    cin>>n;
    cout<<endl;
    cout<<"Inform the elements: "<<endl;
    cout<<endl;

    for(i=0;i<n;i++) {
        for(j=0;j<n;j++) {
            cin>>arr[i][j];
        }
    }
    rotate();
    cout<<endl;
    cout<<"Rotated Matrix"<<endl;
    display();

    return 0;
}

Figure 5. C++ code for rotating the elements of a matrix by 90 degrees.

4. Final considerations

There are several ways to develop code that rotates arrays.
But what would be the importance of this process?
Geometric transformations in the plane are tools in computer graphics for the construction of figures and the production of images. In addition, rotating elements also can be used for data processing.

With this article at OpenGenus, you must have a strong idea of how to rotate matrix of size NxN by 90 degrees (clockwise).