# 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 34 5 6 7 8 9`

Output :

`3 6 92 5 81 4 7`

Test Case 2:

Given:

`1  2  3   45  6  7   89  10 11 1213 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 (Firstelements of 1st row, last row, 1st column and last column) of first cycle in counterclockwise.  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 13 Second 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:

1. 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
2. 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.
3. So run a loop in each cycle from x to N — x — 1, loop counter is y
4. 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)
5. Print the matrix.

Code:

Time Complexity : O(N*N)
Space Complexity : O(1)

# Thanks for Reading

Placewit grows the best engineers by providing an interactive classroom experience and by helping them develop their skills and get placed in amazing companies.

--

--

## More from Placewit

Upskilling students for tech placements!

Love podcasts or audiobooks? Learn on the go with our new app.