Rotate a 2d array in place

Question: Rotate a 2d array in place.

Related Tags:

Rotate in layers

At first glance, we could probably just use an auxillary array to store the top row, then shift the left to top, bottom to left, right to bottom, then place the auxillary row to the right. We then repeat this for each layer. However, we may want to minimize auxillary space and perform this in place.

Algorithm Pseudocode

To perform this in place, we have to move one element at a time. Here is the algorithm pseudocode:

  1. For each layer up to the middle layer:
  2. Start a i.
  3. Start at the top right corner and store it in temp.
  4. Move bottom left corner to top right.
  5. Move bottom right corner to bottom left.
  6. Move top right corner to bottom right.
  7. Increment i in step 3) and repeat until you reach n-1-layer.

Complexity

This algorithm runs in O(1) space and O(n2) time. Since each cell must be moved, we can't do better than this.

Implementation in Java

static void rotateMatrix(int[][] matrix) {

	int n = matrix.length;

	// Not a square matrix
	if (n != matrix[0].length) {
		return;
	}

	// The layer we are currently on
	int currentLayer;
	// Move element up to the last
	int last;
	// temp to store each top cell value in
	int temp;

	// Perform this process per layer up to the middle. 
	// If odd, then the middle element doesn't need to be rotated
	for (int layer = 0; layer < matrix.length / 2; layer++) {

		// Remember that 2d matrices are written as [row][column]

		// From first to last index of the layer array 
		currentLayer = layer;
		last = n - layer - 1;

		// Start from the current layer index 
		for (int i = currentLayer; i < last; i++) {

			// offset for when we go down to next layer
			int offset = i - currentLayer;

			// save top
			// Right Hand Side (RHS) of equation is the left array
			// Takes the current layer, ith column
			temp = matrix[currentLayer][i];

			// Move left to top
			// RHS is left array
			// last-offset signifies moving up a number of rows, depending on which layer we're on
			// column will be our current layer
			matrix[currentLayer][i] = matrix[last-offset][currentLayer];

			// Move bottom to left
			// RHS is bottom array
			// last row, far right side
			matrix[last-offset][currentLayer] = matrix[last][last-offset];

			// Move right to bottom
			// RHS is right array
			// ith row, last column (right)
			matrix[last][last-offset] = matrix[i][last];

			// Move top to right
			matrix[i][last] = temp;

		}

	}

}

Came up with a better solution or have a question? Comment below!