Rotate Matrix K times

Moderate
0/80
Average time to solve is 25m
profile
Contributed by
8 upvotes
Asked in company
Accolite

Problem statement

Ninja is a teacher at a school. He introduced a game of matrix. He gives a square matrix, i.e. N X N matrix, to all the school students and asks them to rotate the matrix ‘K’ times in clockwise direction.

Among them, a student Ninja is new to programming. He doesn’t have much experience, so he asks you to solve the problem. Can you help Ninja to rotate the matrix exactly ‘K’ times clockwise?

Rotation of the matrix here means rotating each row of matrix 'K' times such that the new position of the element having coordinates (i, j) will become (i, (j + K) % N).

For Example:

Let the matrix be and let 'K' will be 1:
1 2 3
4 5 6
7 8 9

The new matrix will be:
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,’ denoting the number of test cases. The test cases follow.
The first line of each test case contains a single integer ‘N’ denoting the number of rows and columns of the matrix respectively.
Next line will contain the integer ‘K’.
The next ‘N’ lines of each test case contain ‘N’ integers in each line.

Output Format:

For each test case, if Ninja managed to solve the problem, print the rotated matrix.

Note:

You don’t need to print anything, it has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 5
2 <= N <= 10 ^ 2
1 <= K <= 10 ^ 2

Time Limit: 1 sec
Sample Input 1:
2 
3
2 
2 2 4
1 3 4
1 2 3
2
1
1 1
1 1
Sample Output 1:
2 4 2 
3 4 1 
2 3 1 

1 1 
1 1
Explanation for Sample Input 1:
In the first test case, the matrix M = [[2,2,4],[1,3,4],[1,2,3]] which on rotating the matrix 2 times, itself yields the matrix as given above. 
In the second test case, the matrix M = [[1,1],[1,1]] which on rotating 1 time yields the same matrix M.
Sample Input 2:
2
2
1
3 6
1 2
3
2
1 2 3
4 5 6
7 8 9
Sample Output 2:
6 3 
2 1 

2 3 1 
5 6 4 
8 9 7
Hint

Can you think of considering each row of matrix as individual arrays and then try to find the pattern?

Approaches (2)
Array Rotation

Consider each row as an array and then rotate the array. This can be done by copying the elements from Kth column to the (N - 1)th  column to the starting of the array using a temporary array and then remaining elements from the start to K - 1 to the end of the array. 

The steps are as follows:

  • Make a temporary array, say ‘arr’ of size ‘N’.
  • Make K as K % N to stay within the size of the matrix.
  • Make an iteration using an iterator pointer ‘i’ from 0 to ‘N - 1’.
  • Now make a nested iteration with the iterator pointer ‘j’ from 0 to ‘N - K -1’ to copy first ‘N - K’ elements into ‘arr’.
  • Make another iteration with an iterator pointer ‘c’ from ‘N - K’ to ‘N - 1’ to copy the elements from ‘K’ to the end starting into ‘arr’.
  • Now copy all the elements from the temporary array ‘arr’ to the given matrix.
  • Return ‘arr’ to the function
Time Complexity

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

 

As we are traversing ‘N’ elements of each row of the matrix and the number of rows is also ‘N’. Therefore, overall time complexity will be O(N * N). 

Space Complexity

O(N), where ‘N’ denotes the number of rows and columns in the matrix.

 

As we are using an extra space for a temporary array to store the elements of the matrix to rotate the rows. Hence, the overall space complexity is O(N).

Code Solution
(100% EXP penalty)
Rotate Matrix K times
Full screen
Console