# Array Algorithm: Rotate an image

An image representing as a 2D matrix. You can take some time to read the problem:

You are given an

`n x n`

2D`matrix`

representing an image, rotate the image by90degrees (clockwise).You have to rotate the image

in-place, which means you have to modify the input 2D matrix directly.DO NOTallocate another 2D matrix and do the rotation.

Example 1:

Input:matrix = [[1,2,3],[4,5,6],[7,8,9]]Output:[[7,4,1],[8,5,2],[9,6,3]]

Example 2:

Input:matrix = [[5,1,9,11],[2,4,8,10],[13,3,6,7],[15,14,12,16]]Output:[[15,13,2,5],[14,3,4,1],[12,6,8,9],[16,7,10,11]]

Example 3:

Input:matrix = [[1]]Output:[[1]]

Example 4:

Input:matrix = [[1,2],[3,4]]Output:[[3,1],[4,2]]

Constraints:

`matrix.length == n`

`matrix[i].length == n`

`1 <= n <= 20`

`-1000 <= matrix[i][j] <= 1000`

# Solution

We will try to rotate on the paper to find the rules on how it rotates. It looks like we just pull out 4 elements top, right, bottom, and left then swap its value.

But how do it continuously? We can think of an iterator from 0 to the size of a row, each iteration just increase i variable straightforward, and the size of a row is equal to the size of the column, then we can play around with the i variable and the length of the row to reach all the matrix positions.

But it is not enough, a matrix may have several layers based on its size, imagine a 3x3 Rubik, you rotate the outside layer but not the center cell, and for the 4x4 matrix, you have no center cell, 2 layers will be rotating. So we can come to the rule of the number of layers like layers = matrix length / 2.

Now we play around with layer, size(length), and i (a row iterator) to reach all the matrix positions. Let resolve a subproblem first.

`var top = matrix[layer][i];`

var right = matrix[i][length - layer];

var bot = matrix[length - layer][length -i];

var left = matrix[length - i][layer];

Look at the positions,

- Top will be fixed the row, only the column moving by i
- Right fixed by the column, only the row moving by i
- Bottom fixed by the row, opposite of the top
- Left fixed by the column, opposite of the right

After pulling out all the four positions, we assign its new position

`// top = left`

matrix[layer][i] = left;

// right = top

matrix[i][length - layer] = top;

// bot = right

matrix[length - layer][length - i] = right;

// left = bot

matrix[length - i][layer] = bot;

The complete code would be.

`public class Solution {`

public void Rotate(int[][] matrix) {

var layers = matrix.Length / 2;

var length = matrix.Length - 1;

for(var layer = 0; layer < layers; layer++){

for(var i = layer; i < length - layer; i++){

var top = matrix[layer][i];

var right = matrix[i][length - layer];

var bot = matrix[length - layer][length -i];

var left = matrix[length - i][layer];

// top = left

matrix[layer][i] = left;

// right = top

matrix[i][length - layer] = top;

// bot = right

matrix[length - layer][length - i] = right;

// left = bot

matrix[length - i][layer] = bot;

}

}

}

}

The time complexity: O(n * n) as we reached all the values of matrix

The space complexity is O(1) as we don’t have any extra space.