如何旋转二维数组

1. Introduction

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:

algorithm ROTATESQUARERIGHT(M):
    // INPUT
    //    M = the square matrix (of order n) to be rotated
    // OUTPUT
    //    The square matrix M, rotated right by 90 degrees in-place

    for i <- 0 to (n / 2) - 1:
        for j <- i to n - i - 1:
            temp <- M[i, j]
            M[i, j] <- M[n - j - 1, i]
            M[n - j - 1, i] <- M[n - i - 1, n - j - 1]
            M[n - i - 1, n - j - 1] <- M[j, n - i - 1]
            M[j, n - i - 1] <- temp

    return M

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:

algorithm ROTATESQUARELEFT(M):
    // INPUT
    //    M = a square matrix of order n
    // OUTPUT
    //    Returns M rotated left by 90 degrees in-place

    for i <- 0 to (n / 2) - 1:
        for j <- i to n - i - 1:
            temp <- M[i, j]
            M[i, j] <- M[j, n - i - 1]
            M[j, n - i - 1] <- M[n - i - 1, n - j - 1]
            M[n - i - 1, n - j - 1] <- M[n - j - 1, i]
            M[n - j - 1, i] <- temp

    return M

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:

algorithm TRANSPOSE(M):
    // INPUT
    //    M = the input matrix (n rows, m columns)
    // OUTPUT
    //    T = the transpose matrix of M

    T = a new m x n matrix

    for i <- 0 to n - 1:
        for j <- 0 to m - 1:
            T[j, i] <- M[i, j]

    return T

Now, the pseudocode of the right rotation for rectangular matrices takes the form:

algorithm ROTATERECTRIGHT(M):
    // INPUT
    //    M = the matrix to be rotated
    // OUTPUT
    //    R = the 90-degree right rotated version of M
    
    R <- TRANSPOSE(M)
    m <- the number of columns in R

    for j <- 0 to (m / 2) - 1:
        Swap columns j and m - j - 1 in R

    return R

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:

algorithm ROTATERECTLEFT(M):
    // INPUT
    //    M = the matrix to rotate
    // OUTPUT
    //    L = the matrix M rotated by 90 degrees left

    L <- TRANSPOSE(M)
    n <- the number of rows in L

    for i <- 0 to (n / 2) - 1:
        Swap rows i and n - i - 1 in L

    return L

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:

algorithm ROTATEHALFWAY(M):
    // INPUT
    //    M = the n x m matrix to rotate
    // OUTPUT
    //    Returns M rotated by 180° in-place

    for i <- 0 to (n / 2) - 1:
        for j <- 0 to m - 1:
            Swap M[i, j] and M[n - i - 1, m - j - 1]

    if n is odd:
        mid <- n / 2
        for j <- 0 to (m / 2) - 1:
            Swap M[mid, j] and M[mid, m - j - 1]

    return M

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 .

6. Conclusion

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.