Rotate matrix to the right
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

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

Question

Rotate matrix to the right

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

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.

Time limit: 1 sec

Accepted Answer

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’:

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

Space Complexity: O(1)Explanation:

O(1)

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

Time Complexity: O(m*n) - For 2d arraysExplanation:

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

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:

Example:

Input Format:

Output Format:

Note:

Constraints:

Top Smart Energy Water Software Developer interview questions & answers

Popular interview questions of Software Developer