Rotate matrix to the right

Moderate
0/80
Average time to solve is 20m
profile
Contributed by
22 upvotes
Asked in companies
AmazonOYOSmart Energy Water

Problem statement

You have been given a matrix ‘MAT’ of size 'N' * 'M' (where 'N' and 'M' denote the number of rows and columns respectively) and a positive integer ‘K’. Your task is to rotate the matrix to the right 'K' times.

Note: 
Right rotation on a matrix is shifting each column to the right side (the last column moves to the first column) and 'K' times means performing this rotation 'K' times.
Example: 
For 'K' = 1 and the given 'MAT':

1 2 3
4 5 6
7 8 9

Output after rotating 'MAT' one time is:

3 1 2 
6 4 5
9 7 8
Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line of input contains an integer 'T' representing the number of test cases.

The first line of each test case contains three single space-separated integers ‘N’, ‘M’, and ‘K’, respectively. ‘N’ and ‘M’ represent the rows and columns of the matrix and ‘K’ denotes the number of right rotations to be performed.

Then each of the next 'N' lines of each test case contains 'M' single space-separated integers representing the elements in a row of the matrix.
Output Format: 
For each test case, return the elements of the matrix row-wise after rotation in a single line.
Note: 
You don't need to print the output, It has already been taken care of. Just implement the given function.
Constraints: 
1 <= T <= 10
1 <= N <= 200
1 <= M <= 200
0 <= K <= 10^9
1 <= MAT[i][j] <= 10^5

Where 'MAT[i][j]' denotes the element in the 'i'th row and 'j'th column of the matrix.

It is guaranteed that sum of 'N' * 'M' over all the test cases does not exceed 10 ^ 5.

Time limit: 1 sec
Sample Input 1 :
2
3 3 2
10 20 30
40 50 60
70 80 90
2 2 2
1 2
3 4
Sample Output 1 :
20 30 10 50 60 40 80 90 70
1 2 3 4
Explanation for Sample Output 1:
In test case 1, Performing right rotation for the first time ('K' = 1) we get:

30 10 20
60 40 50
90 70 80

Performing right rotation for the second time ('K' = 2) we get:

20 30 10
50 60 40
80 90 70

The matrix after rotations will be printed in a single line row-wise. Therefore, the output is:

20 30 10 50 60 40 80 90 70

In test case 2, Performing right rotation for the first time ('K' = 1) we get:

2 1
4 3

Performing right rotation for the second time ('K' = 2) we get:

1 2
3 4

The matrix after rotations will be printed in a single line row-wise. Therefore, the output is:

1 2 3 4
Sample Input 2 :
2
2 3 2
1 2 3
4 5 6
4 4 1
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
Sample Output 2 :
2 3 1 5 6 4
4 1 2 3 8 5 6 7 12 9 10 11 16 13 14 15
Explanation for Sample Output 2:
In test case 1, Performing right rotation for the first time ('K' = 1) we get:

3 1 2
6 4 5

Performing right rotation for the second time ('K' = 2) we get:

2 3 1
5 6 4

The matrix after rotations will be printed in a single line row-wise. Therefore, the output is:

2 3 1 5 6 4

In test case 2, Performing right rotation for the first time ('K' = 1) we get:

4 1 2 3
8 5 6 7
12 9 10 11
16 13 14 15

The matrix after rotations will be printed in a single line row-wise. Therefore, the output is:

4 1 2 3 8 5 6 7 12 9 10 11 16 13 14 15
Hint

Think of rotating each row of the matrix K times to the right.

Approaches (1)
Row-wise rotation

This approach is based on the fact that when we rotate an array to the right by ‘K’ times, it shifts ‘K’ elements from the end to the beginning of the array while the remaining elements shift towards the end. The effective rotations in ‘MAT’ can be from 0 to 'M' - 1, as we get the same matrix ‘MAT’ after every 'M' rotations. So, we will set ‘K’ to ‘K’ % ‘M’.

 

Now, we traverse ‘MAT’ row-wise. We will follow the below steps to rotate the ‘i'-th row of ‘MAT’:

 

  1. First, we reverse all the elements of the row ‘MAT[i]’.
  2. We then reverse the first 'K' elements.
  3. Finally, we reverse the next ‘N’ - 'K' elements.
  4. We will initialize a vector/list ‘result’ and append each row after rotating it.
  5. Finally, we return the ‘result’.
Time Complexity

O(N * M), where ‘N’ and ‘M’ are the number of rows and columns of the given matrix.

 

The time complexity to rotate one row is O(M) and there are total ‘N’ rows. Thus, the overall time complexity will be O(N * M).

Space Complexity

O(1)

 

Since constant space is used, thus the space complexity will be O(1).

Code Solution
(100% EXP penalty)
Rotate matrix to the right
Full screen
Console