You are given an m x n matrix of characters boxGrid representing a side-view of a box. Each cell of the box is one of the following:
'#''*''.'The box is rotated 90 degrees clockwise, causing some of the stones to fall due to gravity. Each stone falls down until it lands on an obstacle, another stone, or the bottom of the box. Gravity does not affect the obstacles' positions, and the inertia from the box's rotation does not affect the stones' horizontal positions.
It is guaranteed that each stone in boxGrid rests on an obstacle, another stone, or the bottom of the box.
Return an n x m matrix representing the box after the rotation described above.
Example 1:
Input: boxGrid = [["#",".","#"]] Output: [["."], ["#"], ["#"]]
Example 2:
Input: boxGrid = [["#",".","*","."], ["#","#","*","."]] Output: [["#","."], ["#","#"], ["*","*"], [".","."]]
Example 3:
Input: boxGrid = [["#","#","*",".","*","."], ["#","#","#","*",".","."], ["#","#","#",".","#","."]] Output: [[".","#","#"], [".","#","#"], ["#","#","*"], ["#","*","."], ["#",".","*"], ["#",".","."]]
Constraints:
m == boxGrid.lengthn == boxGrid[i].length1 <= m, n <= 500boxGrid[i][j] is either '#', '*', or '.'.In this approach, first simulate the effect of gravity on the stones in the box before rotating the box 90 degrees clockwise. To simulate gravity, traverse each row from right to left, moving stones to the right until they hit an obstacle or stack upon other stones. Once every stone has settled due to gravity, create a new matrix representing the rotated box by converting rows into columns.
This Python solution iterates through each row of the box matrix from right to left, simulating the effect of gravity by moving stones ('#') to the rightmost available positions and stopping if an obstacle ('*') is encountered. After gravity is applied, the matrix is transposed to achieve a 90 degrees clockwise rotation.
C++
Time Complexity: O(m * n), where m is the number of rows and n is the number of columns in the matrix. This complexity comes from the need to process each element when simulating gravity and then again when transposing.
Space Complexity: O(1) if we ignore the space for the output result that is unavoidable for transposing the matrix.
This approach creates a new matrix to represent the rotated version of the box. After initializing the new transposed matrix, simulate the gravitational fall of each stone by placing them in the correct positions in the new matrix. This is achieved by iterating through the rotated columns and calculating the final position of each stone.
The Java solution pre-allocates a rotated matrix, initializes it with empty spaces, and directly simulates the effects of gravity as each stone is repositioned in the rotated matrix. This approach eliminates the need for a separate gravity simulation phase before rotation.
JavaScript
Time Complexity: O(m * n) because transposing and simulating stone drops require us to iterate through all elements.
Space Complexity: O(m * n) for storing the rotated matrix.
| Approach | Complexity |
|---|---|
| Simulate Gravity and Then Rotate | Time Complexity: O(m * n), where m is the number of rows and n is the number of columns in the matrix. This complexity comes from the need to process each element when simulating gravity and then again when transposing. |
| Transpose and Simulate Gravity Directly | Time Complexity: O(m * n) because transposing and simulating stone drops require us to iterate through all elements. |
Rotating the Box - Leetcode 1861 - Python • NeetCodeIO • 8,915 views views
Watch 9 more video solutions →Practice Rotating the Box with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor