# Solution

**Algorithm**

We begin by understanding how to rotate a 2x2, 3x3, and 4x4 matrix to understand the algorithm.

- In order to rotate a 2x2 matrix,
- The element at [0,0] is swapped with the element at [0,1], [1,1], and [1,0] in that order.

- In order to rotate a 3x3 matrix,
- The element at [0,0] is swapped with the element at [0,2], [2,2], and [2,0] in that order.
- The element at [0,1] is swapped with the element at [1,2], [2,1], and [1,0] in that order.

- In order to rotate a 4x4 matrix
- The element at [0,0] is swapped with the element at [0,3], [3,3], and [3,0] in that order.
- The element at [0,1] is swapped with the element at [1,3], [3,2], and [2,0] in that order.
- The element at [0,2] is swapped with the element at [2,3], [3,1], and [1,0] in that order.
- The last step involves rotating the inside 2x2 matrix the exact same way the 2x2 matrix is rotated above.
- The element at [1,1] is swapped with the element at [1,2], [2,2], and [2,1] in that order.

### Java Solution

```
class Solution {
public void rotate(int[][] matrix) {
int last = matrix.length - 1;
int level = 0;
int numOfLevels = matrix.length/2;
while(level < numOfLevels){
for(int i=level; i<last; i++){
swap(level, i, i, last, matrix);
swap(level, i, last, last - i + level, matrix);
swap(level, i, last - i + level, level, matrix);
}
level++;
last--;
}
}
void swap(int i1, int j1, int i2, int j2, int[][] arr){
int t = arr[i1][j1];
arr[i1][j1] = arr[i2][j2];
arr[i2][j2] = t;
}
}
```

**Complexity Analysis**

- Time complexity : O(n)