Rotate an array by 90 degrees

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:

// Rotate NxN int matrix in-place
// This is an inplace transpose, followed by an inplace reflection along y direction in the middle
public static void inplace_rotate(int[][] arr){
  inplace_transpose(arr);
  inplace_reflect(arr);
}

// pre: arr is square
public static void inplace_reflect(int[][] arr){
  int size = arr.length;
  for(int k=0; k < size; k++){
    for(int i=0; i < Math.floor(size/2); i++){
      swap(arr, k, i, k, size-i-1);
    }			
  }
}

// pre: matrix is square
public static void inplace_transpose(int[][] arr){
  int size = arr.length;
  for(int diag = 0; diag < size; diag++){
    for(int i=diag+1; i<size; i++){
      swap(arr, diag, i, i, diag);
    }
  }
}

// Swaps elements of int array
public static void swap(int[][] arr, int row1, int col1, int row2, int col2){
  int num1 = arr[row1][col1];
  int num2 = arr[row2][col2];
  arr[row1][col1] = num2;
  arr[row2][col2] = num1;
}