Last Updated: 1 Oct, 2021
Rotate the Box
Moderate
Asked in company
You are given a box of height ‘N’ and width ‘M’. Each cell of the box may contain:
1) A fixed obstacle denoted by ‘ * ’
2) A stone denotes by ‘ # ’
3) Empty space denoted by ‘ . ’
Initially the box is placed on the ground and due to gravity all the stones lie either on the lowest cells in their column, or a stone may be supported by another stone or by the fixed obstacle beneath it.
You now rotate the box 90 degrees clockwise, so its height becomes ‘M’ and its width becomes ‘N’, re-aligning all of the stones. But as stated previously, the obstacles are fixed and won’t change their relative positions. You have to find the new alignment of the box after the rotation.
Note :
You may consider the stones to be heavy and rotational force has no effect on them. That is: the stones do not re-align themselves during the rotation.
For Example :
If N = 1 and M = 6 and box is:
‘#’ , ‘.’ , ‘.’ , ‘*’ , ‘#’ , ‘.’
The box after rotation becomes:
‘.’
‘.’
‘#’
‘*’
‘.’
‘#’
Input Format :
The first line contains a single integer ‘T’ denoting the number of test cases, then each test case follows:
The first line of each test case contains two integers ‘N’ and ‘M’ denoting the dimensions of the box initially.
The next ‘N’ lines each contain ‘M’ characters denoting the cell of the box.
Output Format :
For each test case, print the box after re-aligning, the new box is of dimensions M*N.
Output for each test case will be printed in a separate line.
Note :
You are not required to print anything; it has already been taken care of. Just implement the function.
Constraints :
1 ≤ T ≤ 10
1 ≤ N, M ≤ 250
Box[i][j] = { ‘ * ’ , ‘ # ‘ , ‘ . ‘ }
Time limit: 1 sec
Approaches
We can simply shift all the stones first, and then rotate the matrix, this will be our final result and we won’t have to re-align the stones after the rotation!
Why? Try to imagine what happens after rotation!
The rotation simply pushes all the boxes to extreme right positions. We can simply take that effect into account first on the N*M matrix and after that simply rotate the box without making re-alignments and returning an M*N matrix.
To shift the elements to the extreme right. Use a pointer to keep the track of the rightmost available cell for a stone. To implement it, simply consider each row at a time, and initialize a pointer to point to the last column initially. Now while iterating the row from right to left, if you encounter a stone ‘#’, then simply swap it with the cell pointer by pointer and decrement the value of the pointer, and in case you encounter an obstacle ‘*’ then change the value of the pointer to point to the left cell of the obstacle.
In the end, simply rotate the box and return it.
The steps are as follows :
- Run a loop for variable ‘i’ from 0 to N, to iterate through each row at a time.
- Initialize a pointer ‘ptr’, and set its value equal to M-1.
- Run an inner-loop for variable ‘j’ from M-1 to 0, to iterate elements of each row.
- If the element at Box[i][j] is a stone then swap Box[i][j] and Box[i][ptr], and also decrement the value of ‘ptr’.
- If the element at Box[i][j] is an obstacle then set the value of ‘ptris ’ equal to j-1.
- Initialize a 2-D matrix ‘rotatedBox’ to store the final answer.
- To rotate the box simply iterate each row from right to left and start filling the matrix ‘rotatedBox’.
- Finally, return the matrix ‘rotatedBox’.
Similar problems