Rotate Clockwise

Easy
0/40
Average time to solve is 15m
profile
Contributed by
6 upvotes
Asked in companies
Vir SoftechColoredcow

Problem statement

You are given a square matrix of dimensions ‘N * N’. You have to rotate the matrix 90 degrees in a clockwise direction.

EXAMPLE: 
Input: 'N' = 2, 'NUMS' = [[1, 2], [3, 4]]

Output: [[3, 1], [4, 2]]

Here the given matrix is rotated 90 degrees in a clockwise direction.
Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line of the input contains an integer, 'T’, denoting the number of test cases.

The first line of each test case will contain a single integer ‘N’, denoting the dimension of the matrix.

Each of the next ‘N’ lines contains ‘N’ integers separated by single spaces denoting the elements of the square matrix ‘NUMS’.
Output format : 
For each test case, print the matrix after rotating 90 degrees in a clockwise direction.
Note : 
You don't need to print anything. It has already been taken care of. Just implement the given function.
Constraints : 
1 <= 'T' <= 10
2 <= 'N' <= 10^2
1 <= 'NUMS[i]' <= 10^5

Time Limit: 1 sec
Sample Input 1 :
2
2
1 2
3 4
3
1 2 3
4 5 6
7 8 9
Sample Output 1 :
3 1
4 2
7 4 1
8 5 2
9 6 3
Explanation Of Sample Input 1 :
For the first test case,
'N' = 2, 'NUMS' = [ [1, 2], [3, 4]]
After rotation 90 degrees in a clockwise direction the matrix will be:
‘NUMS’ = [ [3, 1], [4, 2] ].

For the second test case,
'N' = 3, 'NUMS' = [ [1, 2, 3], [4, 5, 6], [7, 8, 9] ]
After rotation 90 degrees in a clockwise direction the matrix will be:
‘NUMS’ = [ [7, 4, 1], [8, 5, 2], [9, 6, 3] ].
Sample Input 2 :
2
3
5 10 4
10 6 2
10 3 3
3
3 8 2
10 3 9
6 3 2
Sample Output 2 :
10 10 5 
3 6 10 
3 2 4 
6 10 3 
3 3 8 
2 9 2
Hint

What will be the transpose of a matrix?

Approaches (1)
Transpose

The idea of this approach is to relate the clockwise rotation of the square matrix to the transposition of the matrix. In the transposition of the matrix, the ith column of the original matrix becomes the ith row after the transposition. After rotation of the matrix, 90 degrees in a clockwise direction the ith column of the original matrix becomes the ith row in reverse order. Hence, we find the transpose of the matrix and then reverse the rows of the transposed matrix to get our desired output.

 

Algorithm :  

  • Iterate over each row of the matrix (say iterator ‘i’)
    • Iterate from ‘i + 1’ to ‘N - 1’ (say iterator ‘j’)
      • swap(NUMS[i][j], NUMS[j][i]).
  • Iterate over each row of the matrix (say iterator ‘i’)
    • Declare two integers ‘l’ and ‘r’ and initialize them with 0 and ‘N’ - 1 respectively.
    • while (‘l’ is less than ‘r’)
      • swap(NUMS[i][l], NUMS[i][r]).
      • l += 1, r -= 1.
Time Complexity

O(N*N), where ‘N’ is the dimension of the matrix.
 

Transposition of the matrix takes O(N*N) time and reversing the rows of the matrix takes O(N*N) time.

Hence, the overall time complexity will be O(N*N).

Space Complexity

O(1)

 

We are not using any extra space.

Hence the overall space complexity will be O(1).

Code Solution
(100% EXP penalty)
Rotate Clockwise
Full screen
Console