Rotate the Box

Moderate
0/80
Average time to solve is 20m
profile
Contributed by
1 upvote
Asked in company
Uber

Problem statement

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:
 ‘.’
 ‘.’  
 ‘#’
 ‘*’
 ‘.’ 
 ‘#’
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1 :
2
1 6
# . . * # .
2 3
# . .
# # .
Sample Output 1 :
.
.
#
*
.
#
. .
# .
# #
Explanation For Sample Input 1 :
For test case 1 : 
After rotation of the box by 90 degrees, the 1*6 box will now be 6*1, and the stone at (0, 0) will fall down to (2, 0) to now be supported by the fixed obstacle beneath it at (3, 0). And the stone at (4, 0) will fall down to (5, 0) to now be supported by the ground.


For test case 2 : 
After rotation of the box by 90 degrees, the 2*3 box will now be 3*2, and as there is no obstacle so all the stones will now fall towards the ground.
Sample Input 2 :
2
1 1 
#
3 1
#
*
.
Sample Output 2 :
#
. * #
Hint

Assume that gravity is applied from the right side instead of from the bottom.

Approaches (1)
Brute Force Approach

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’.
Time Complexity

O( N * M ), where N and M denote the height and width of the box



Each element in the matrix is visited exactly once while re-aligning it and later when we rotate the matrix we visit each of the element exactly once. Hence the time complexity is O( N*M ).

Space Complexity

O( N * M ), where N and M denote the height and width of the box



We construct a matrix of M*N that denotes the matrix after rotation, an auxiliary space of order ~(N*M) is used. Hence the space complexity is O( N*M ).

Code Solution
(100% EXP penalty)
Rotate the Box
Full screen
Console