Rotate an array by 90 degrees

Posted on August 2, 2013

Last updated on August 2, 2013

Problem Statement:

Given an $$N \times K$$ array of integers, rotate the array 90 degrees clockwise. Improve the algorithm to do this inplace for square arrays.

As an example, the following array

$\left( \begin{array}{cccc} 1 & 2 & 3 & 4 \\ 5 & 6 & 7 & 8 \\ 9 & 10 & 11 & 12 \end{array} \right)$

rotated by 90 degrees clockwise is:

$\left( \begin{array}{ccc} 9 & 5 & 1 \\ 10 & 6 & 2 \\ 11 & 7 & 3 \\ 12 & 8 & 4 \end{array} \right)$

The trivial solution that is not inplace is to allocate a new array. Start with the bottom row of the input, and make it the first column of the output. Work your way through all the rows like this.

For a square array, we can do this inplace. First, notice that a 90 degree clockwise rotation is a matrix transpose, followed by a reflection (or if you prefer, a rotation), along the center of the array in the vertical direction. This leads to the following algorithm in Java: