# 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!

Next Challenge: