Last Updated: 28 Nov, 2020
Rotate Matrix K times
Moderate
Asked in company
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
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
Approaches
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
The idea is to rotate each row K times, K % N *K elements from the back end of the array come to the front and the rest of the elements from the front shift backwards.
In this approach, we firstly reverse all the elements of the array. Then, reversing the first K elements followed by reversing the rest N - K * N - K elements give us the required result.
Approach:
- First iterate the rows with the help of iterator pointer ‘i’ .
- Reverse the elements of the ith row.
- Reverse the first ‘K’ elements of the row.
- Now reverse the last ‘K’ elements of the row.
- Return ‘arr’ to the function.