Given an NxN array, rotate it 90 degrees without making a new array

Given an NxN array, rotate it 90 degrees without making a new array

Example:

rotate90(\[\[1,2,3],\[4,5,6],\[7,8,9]])
> \[\[7,4,1],\[8,5,2],\[9,6,3]]

Oh boy, matrix operations, isn’t that fun?

This problem seems to require some visualization first, so I’ll grab my pen and I’ll start drawing stuff before trying to implement it, will that help? (I’m writing this post after figuring it out, so I guess it did! ¯\_(ツ)_/¯)

Looking for the simplest case (n=2)

Notes 1

In this matrix (2x2) we need to make 4 operations:

  • Top-Left —> Top-Right
  • Bottom-Left —> Top-Left
  • Bottom-Right —> Bottom-Left
  • Top-Right —> Bottom-Right

Sounds easy, but what happens when we have more?

Moving rings!

We can imagine our matrices as compositions of rings, and we need to rotate every ring individually

For the example given, we just need to rotate the external ring, and the 5 in the middle stays as it is.

Notes 2

It gets more interesting when we have a higher n:

Notes 3

With n = 4 we have to rotate 2 rings, and the number of rings increases with every 2 increments in n (we can probably say that number of rings = n / 2).

Rotating a ring, general case

Let’s try to extract the general rule for rotating an individual ring, I’ll use a higher n for that, since it was difficult to extract it from the simplest case:

Notes 4

We need to traverse all the positions - 1 inside a ring and make the move operations. The exact operations depend on the movement, and we need to keep one item in memory since it will be overriden after one of the operations.

This is the operation for Top —> Right

Notes 5

We need to write similar operations for the other movements.

Solution

/**
 * Rotates the incoming matrix 90deg
 * @param matrix
 */
function rotate90deg(matrix: unknown[][]): void {
  const n = matrix.length === 0 ? 0 : matrix[0].length

  for (let ring = 0; ring < Math.floor(n / 2); ring++) {
    for (let position = ring; position < n - ring - 1; position++) {
      const backupRight = matrix[position][n - ring - 1]

      // Top -> Right
      matrix[position][n - ring - 1] = matrix[ring][position]

      // Left -> Top
      matrix[ring][position] = matrix[n - position - 1][ring]

      // Bottom -> Left
      matrix[n - position - 1][ring] = matrix[n - ring - 1][n - position - 1]

      // Right -> Bottom
      matrix[n - ring - 1][n - position - 1] = backupRight
    }
  }
}

This should do the trick, I have to confess that I needed to implement tests to ensure I didn’t mess up with the movement operations (TDD FTW!).

Big-O complexity for this one should be something like O(n / 2 * n / 2) -> O(n^2) although I’m not completely sure if this is correct… so we can leave it as trust me, this is fine :D

Given an NxN array, rotate it 90 degrees without making a new array