Problem

Given a 2D array, rotate the array by 90 degrees.

Input

• A: 2D array of size greater than \(n\) \times \(m\)
  • \(n\geq0, m\geq0\)

Approach

This is a very commonly asked problem, with a conceptual approach that is easy to visualize but difficult to implement in code.

Animation by https://galencorey.wordpress.com/2016/11/18/rotating-a-matrix-with-gifs/

Optimized Solution

I encounter this problem many times over the years, often stumbling in the same way at the coding part.

The key to solving this problem lies in cleanliness. Yes, although the animated gif above shows how the rotation works conceptually, putting this into an algorithm can get very confusing simply due to the index and offset values that we have to keep juggling around.

If you are in the same category as I am, then my recommendations are as follows:

• Define a function solely for the rotation
• Have the rotation function take minimum and maximum boundaries of a square as inputs.
  • For example, r1 would represent the topmost row of the current inner square. r2 would represent the bottommost row. c1 would represent the leftmost column, and c2 would represent the rightmost column.
• Have the rotation function also take an offset value, so that we can offset the rotation pattern like in the animation above.

The practical optimization for this problem is to just reduce the loop range by half as the square to process iteratively gets smaller and smaller until it reaches the middle. This part however is easier than the actual rotation algorithm itself.

    def rotate(self, matrix: List[List[int]]) -> None:
        """
        Do not return anything, modify matrix in-place instead.
        """
        size = len(matrix)

        def swap(matrix, r1, c1, r2, c2, offset):
            temp = matrix[r1 + offset][c2]
            matrix[r1 + offset][c2] = matrix[r1][c1+offset]

            temp2 = matrix[r2][c2-offset]
            matrix[r2][c2-offset] = temp

            temp3 = matrix[r2-offset][c1]
            matrix[r2-offset][c1] = temp2

            matrix[r1][c1+offset] = temp3

        for i in range(0, size // 2):
            c1 = r1 = i
            c2 = r2 = size - 1 - i
            for offset in range(c2 - c1):
                swap(matrix, r1, c1, r2, c2, offset)

Advanced Solutions

Let \(A(m, n)\) be the point in the original 2D matrix \(A\), where \(m\) is the row number and \(n\) is the column number. \(\tilde{A}\) is the rotated matrix.

The key to solving this problem is to observe that a row in the original 2D array \(A\) becomes a column in the rotated 2D array.

Lets look at the values in the first row.

• \(A(0, 0)\) \(\rightarrow\) \(\tilde{A}(0, 2)\)
• \(A(0, 1)\) \(\rightarrow\) \(\tilde{A}(1, 2)\)
• \(A(0, 2)\) \(\rightarrow\) \(\tilde{A}(2, 2)\)

And the second row:

• \(A(1, 0)\) \(\rightarrow\) \(\tilde{A}(0, 1)\)
• \(A(1, 1)\) \(\rightarrow\) \(\tilde{A}(1, 1)\)
• \(A(1, 2)\) \(\rightarrow\) \(\tilde{A}(2, 1)\)

We can see that \(m\) and \(n\) is mapped a certain way into \(\tilde{A}\).

• \(\tilde{y}\) = \(x\)
• \(\tilde{x}\) = \(y_\max - y\)

The solutions below were written years ago and are still applicable for Pythonistas who like Python shortcuts (such as the ~ operator) to write as little code as possible. I would only recommend these if you fully understand how to solve this problem with the above approach.

Brute Force Solution

def rotate_2d_array_brute_force(A):  
    copy = [[0] * len(A) for _ in range(0, len(A))]

    for j in range(0, len(A)):
        for i in range(0, len(A)):
            copy[i][j] = A[~j][i]

    return copy

Note that ~j is equivalent to -(j + 1). When used as an index of a list, it could also be interpreted as j + 1 values from the right.

This algorithm requires \(O(n^2))\) space complexity and \(O(n^2))\) time complexity

Approach #2

The optimized approach has a very straightforward strategy that you can follow. To rotate a matrix by 90 degrees, it takes two simple steps:

1. Transpose the matrix (rows turn into columns, vice-versa)
2. Flip the values of each row (\([1, 2, 3, 4] => [4, 3, 2, 1]\))

Each step can be done as a separate nested for loop:

# Transpose
m = len(matrix)  
n = len(matrix[0])  
for i in range(0, m):  
    for j in range(i, n):
        matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]

# Rotate horizontally
for i in range(0, m):  
    for j in range(0, n // 2):
        matrix[i][j], matrix[i][n-j-1] = matrix[i][n-j-1], matrix[i][j]

Approach #3

This solution reduces the need for two nested for loops, but it requires some tricky array manipulation and some Python tricks.

The idea is quite straightforward on a \(3 \times 3\) matrix:

• Cache the value of \(A(0, 2)\) and set \(A(0, 2)\) \(\rightarrow\) \(\tilde{A}(0, 0)\)
• Cache the value of \(A(2, 2)\) and set \(\tilde{A}(2, 2)\) to the previous cached value
• Cache the value of \(A(2, 0)\) and set \(\tilde{A}(2, 0)\) to the previous cached value
• Set \(\tilde{A}(0, 0)\) to the previous cached value
• Repeat with the inner rows/columns

Although this idea is straightforward, it will take a bit more effort to translate this into a formula.

One way to build up this formula is to try a few more example cases.

For example, on the first pass of a \(4 \times 4\) matrix, you will access these indices.

• \(A(0, 0)\)
• \(A(0, 3)\)
• \(A(3, 3)\)
• \(A(3, 0)\)

On the second pass, you will access these indices.

• \(A(0, 1)\)
• \(A(1, 3)\)
• \(A(3, 2)\)
• \(A(2, 0)\)

On the third pass, you will access these indices.

• \(A(0, 2)\)
• \(A(2, 3)\)
• \(A(3, 1)\)
• \(A(1, 0)\)

When do we stop swapping?

We stop swapping when we have successfully swapped each value in the leftmost, topmost, rightmost, and bottommost values. This could be labeled as the outermost cycle. Once this cycle is complete, we will have to start swapping again for the next innermost cycle.

In a \(3 \times 3\) matrix, we only need 1 cycle (the center value will never change!).
In a \(4 \times 4\) matrix, we need 2 cycles because the four center values can be rotated.
In a \(5 \times 5\) matrix, we need 2 cycles again; 1 cycle for the \(3 \times 3\) matrix in the center, and 1 cycle for the outermost boundary.

Thus, the number of cycles corresponds to the number of elements in a row or column: len(A) // 2

def rotate_2d_array(A):  
    for j in range(0, len(A) // 2):
        for i in range(j, len(A) - 1 - j):
            old = A[j][i]
            A[i][~j], old = old, A[i][~j]
            A[~j][~i], old = old, A[~j][~i]
            A[~i][j], old = old, A[~i][j]

            A[j][i] = old

    return A