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 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.

Learn more at Placewit. Follow us on Instagram and Facebook for daily learning.