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 '.'.The key idea in #1861 Rotating the Box is to simulate gravity on stones before or after performing a 90-degree clockwise matrix rotation. Each cell may contain a stone (#), an obstacle (*), or empty space (.). When the box rotates, stones fall downward until they hit an obstacle or another stone.
A practical strategy is to process each row using a two-pointer technique. Start scanning from the right side of the row, treating it as the "bottom" after rotation. Maintain a pointer that marks the next available position where a stone can fall. When encountering a stone (#), move it to the rightmost available slot. If an obstacle (*) appears, reset the pointer to the position just left of the obstacle since stones cannot pass through it.
After simulating gravity within each row, perform a matrix rotation to construct the final grid. This approach efficiently models the physics of falling stones while keeping the implementation clean. The algorithm runs in linear time relative to the number of cells.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Row Gravity Simulation + Matrix Rotation | O(m × n) | O(m × n) |
| In-place Gravity with Two Pointers | O(m × n) | O(1) extra (excluding output) |
NeetCodeIO
Use these hints if you're stuck. Try solving on your own first.
Rotate the box using the relation rotatedBox[i][j] = box[m - 1 - j][i].
Start iterating from the bottom of the box and for each empty cell check if there is any stone above it with no obstacles between them.
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.
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.
1def rotateBox(boxGrid):
2 m, n = len(boxGrid), len(boxGrid[0])
3 for r in range(m):
4 # Apply gravity
5 free_space = n - 1
6 for c in range(n - 1, -1, -1):
7 if boxGrid[r][c] == '#':
8 boxGrid[r][free_space], boxGrid[r][c] = '#', '.'
9 free_space -= 1
10 elif boxGrid[r][c] == '*':
11 free_space = c - 1
12 # Rotate the box 90 degrees clockwise
13 rotated_box = zip(*boxGrid[::-1])
14 return [list(row) for row in rotated_box]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.
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.
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.
1function rotateBox(boxGrid) {
2Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Matrix manipulation and simulation problems like Rotating the Box are common in technical interviews, including FAANG-style interviews. They test understanding of arrays, coordinate transformations, and careful handling of edge cases.
A 2D array (matrix) is the most suitable data structure for this problem. It allows efficient row traversal, element swapping, and construction of the rotated matrix after simulating gravity.
The optimal approach simulates gravity on each row using a two-pointer technique and then performs a 90-degree clockwise matrix rotation. This ensures stones settle correctly before producing the rotated result. The overall complexity is linear in the number of cells.
Simulating gravity within each row simplifies the logic because stones effectively fall to the right in the original orientation. Afterward, rotating the matrix converts that rightward movement into downward movement in the final box.
The JavaScript solution mirrors the logic utilized by the Java version, setting up the rotated matrix initially, processing each cell to account for gravitational shifts, and adjusting the resultant matrix positions directly during the processing stage.