In this topic, we’ll explain how to rotate a two-dimensional array. We’ll observe both right and left rotations.
2. Preliminary Notes
A two-dimensional array is basically a two-dimensional matrix. So, without losing any generality, we can assume our two-dimensional array is a two-dimensional matrix of elements. Let’s observe the following matrix, where each distinct element is colored differently:
It’s a matrix. Below are the right and left rotations of the matrix by :
And below is the right rotation of the matrix by :
Note that the left rotation by is basically the same as the right rotation by .
Additionally, it’s straightforward to note that the right rotation by is the same as three right rotations by or one left rotation by . And any rotation is basically no rotation. Thus, to cover all the 90-angled rotation configurations, it suffices to only observe the cases of the left and right rotations by and the rotation by .
If we put aside the optimal number of steps to perform a rotation, then the right rotation by is enough to reproduce all the 90-angled rotation configurations. However, that may not be optimal in the number of steps performed.
3. Custom Case: Square Matrix
First, let’s develop the rotation algorithm for a custom case when the matrix is square. To make the algorithm obvious, let’s divide our square matrix into quadrants as depicted below:
Now, the left and right rotations by take the form:
As we can see, we can enumerate elements in a quadrant and replace them with elements in the neighboring quadrants. The picture below illustrates the idea more precisely:
In the picture above, is the size of the matrix side. As we can see, during the right rotation by , the element with the position rotates to the position , the element rotates to the position , the element rotates to the position , and finally, the element rotates to the position . Shortly, there’s a four-step circular exchange happening between the appropriate elements in the matrix. Note that our indexing is zero-based.
3.1. Right Rotation Algorithm
Here’s the pseudocode of the right rotation algorithm:
3.2. Left Rotation Algorithm
The pseudocode of the left rotation is very similar to the right rotation, except the order of exchange is the opposite:
4. Common Case: Rectangular Matrix
The rotation algorithms described above only work for square matrices. For matrices that aren’t square, i.e., for rectangular matrices, we need to develop separate algorithms. First, let’s recall what the transpose matrix of the original matrix is. is a matrix where column is the row in .
In the example below, a matrix is transformed into a transpose matrix:
We can see that transposing partially performed the right rotation task: the rows are rotated, but the column order isn’t what we need. Thus, we additionally swap the symmetric columns: for a matrix with columns, we swap columns and , then and , and so on. Shortly, the right rotation by can be achieved by transposing followed by the symmetric column swap operation.
4.1. Right Rotation Algorithm
First, let’s provide the pseudocode for transposing matrices:
Now, the pseudocode of the right rotation for rectangular matrices takes the form:
4.2. Left Rotation Algorithm
Similarly to the right rotation, left rotation is performed by transposing followed by the symmetric row swap operation. The pseudocode is below:
The algorithms of left and right rotations for rectangular matrices can be used for square matrices as well. They’ll produce correct results, though they aren’t as optimal in the number of steps as the custom algorithms for square matrices. Anyway, asymptotically, they’re the same.
4.3. Rotation Algorithm
Finally, let’s provide the pseudocode for the rotation algorithm. The algorithm is actually optimal for any matrix so that it can be readily used for square matrices as well:
5. Complexity Analysis
All the algorithms described in this topic have complexity, where is the number of rows and is the number of columns in a matrix. In the case of square matrices, the complexity simply becomes .
In this topic, we’ve gone through algorithms for rotating two-dimensional matrices. First, we’ve developed optimal algorithms for square matrices, and then we’ve provided rotation algorithms for common rectangular matrices. As we’ve noted, the rotation algorithms for rectangular matrices can be used for square ones as well, though the custom algorithms are better in the number of steps. The rotation algorithm is optimal for any matrix.