# Inplace Rotate Square Matrix— Asked in Amazon Interviews

# Problem Statement :

You are given a square matrix. Find a way to turn the matrix by 90 degrees in an anti-clockwise direction without any extra space.

**Given:**

**Test Case 1:**

**Given:**

`1 2 3`

4 5 6

7 8 9

**Output** :

`3 6 9`

2 5 8

1 4 7

**Test Case 2:**

**Given:**

`1 2 3 4`

5 6 7 8

9 10 11 12

13 14 15 16

**Output:**

`4 8 12 16 `

3 7 11 15

2 6 10 14

1 5 9 13

**Explanation of test cases :**

To solve the question without any extra space, rotate the array in form of squares, dividing the matrix into squares or cycles.

*For example,*

A 4 X 4 matrix will have 2 cycles. The first cycle is formed by its 1st row, last column, last row, and 1st column. The second cycle is formed by the 2nd row, second-last column, second-last row, and 2nd column. The idea is for each square cycle, swap the elements involved with the corresponding cell in the matrix in an anti-clockwise direction i.e. from top to left, left to bottom, bottom to the right, and from right to top one at a time using nothing but a temporary variable to achieve this.

**Demonstration:**

First Cycle (Involves Red Elements)

1 2 3 4

5 6 7 8

9 10 11 12

13 14 15 16 Moving first group of four elements (First

elements of 1st row, last row, 1st column

and last column) of first cycle in counter

clockwise.

4 2 3 16

5 6 7 8

9 10 11 12

1 14 15 13

Moving next group of four elements of

first cycle in counter clockwise

4 8 3 16

5 6 7 15

2 10 11 12

1 14 9 13 Moving final group of four elements of

first cycle in counter clockwise

4 8 12 16

3 6 7 15

2 10 11 14

1 5 9 13Second Cycle (Involves Blue Elements)

4 8 12 16

3 6 7 15

2 10 11 14

1 5 9 13 Fixing second cycle

4 8 12 16

3 7 11 15

2 6 10 14

1 5 9 13

**Algorithm:**

- There are N/2 squares or cycles in a matrix of side N. Process a square one at a time. Run a loop to traverse the matrix a cycle at a time, i.e loop from 0 to N/2–1, the loop counter is
*i* - Consider elements in a group of 4 in the current square, rotate the 4 elements at a time. So the number of such groups in a cycle is N — 2*i.
- So run a loop in each cycle from x to N — x — 1, loop counter is
*y* - The elements in the current group is (x, y), (y, N-1-x), (N-1-x, N-1-y), (N-1-y, x), now rotate the these 4 elements, i.e (x, y) <- (y, N-1-x), (y, N-1-x)<- (N-1-x, N-1-y), (N-1-x, N-1-y)<- (N-1-y, x), (N-1-y, x)<- (x, y)
- Print the matrix.

**Code:**

Time Complexity : O(N*N)

Space Complexity : O(1)