Rotating the Box
You are given an m x n matrix representing the side-view of a box. Each cell is either a stone ('#'), an obstacle ('*'), or empty ('.'). The box is rotated 90 degrees clockwise, and gravity causes stones to fall down. Return the resulting matrix.
That is LeetCode 1861: Rotating the Box. The problem sounds like you need to simulate physics in two dimensions, but it breaks down into two clean, independent steps.
Why this problem matters
Rotating the Box combines two common interview patterns into one problem: in-place array rearrangement (simulating gravity) and matrix rotation. Neither step is difficult on its own, but the key insight is recognizing that you should apply gravity before rotating, not after. That ordering simplifies the problem dramatically.
This problem also tests whether you can work with matrix transformations methodically. If you try to do gravity and rotation simultaneously, the logic gets tangled. If you separate them, each step is something you have likely solved before.
The approach: gravity first, rotate second
The trick is to realize that gravity in the original orientation acts horizontally (stones slide right within each row). After rotation, that rightward slide becomes a downward fall. So you can:
- Simulate gravity on the original grid by sliding stones rightward within each row.
- Rotate the grid 90 degrees clockwise.
Why gravity first? In the original grid, gravity within a row is a simple one-dimensional operation. Each row is independent. You walk right to left, and whenever you see a stone, you move it to the rightmost available empty cell (tracked by a pointer). Obstacles reset the pointer.
After this step, the grid already has stones in their correct "fallen" positions relative to the original orientation. Rotating the grid then just rearranges the cells into the new orientation.
Applying gravity within rows (before rotation) is simpler than applying gravity within columns (after rotation) because row-based operations avoid column-stride memory access. It also avoids needing to create the rotated grid first and then modify it in place.
The solution
def rotateTheBox(box: list[list[str]]) -> list[list[str]]:
m, n = len(box), len(box[0])
for row in box:
empty = n - 1
for col in range(n - 1, -1, -1):
if row[col] == "*":
empty = col - 1
elif row[col] == "#":
row[col] = "."
row[empty] = "#"
empty -= 1
rotated = [[box[m - 1 - r][c] for r in range(m)] for c in range(n)]
return rotated
The first loop handles gravity. For each row, empty tracks the rightmost position where a stone can land. We scan from right to left. When we hit an obstacle, empty resets to just left of it. When we hit a stone, we move it to the empty position and decrement empty.
The second part builds the rotated matrix. A 90-degree clockwise rotation maps position (r, c) in the original to position (c, m - 1 - r) in the result. We construct the new grid using a list comprehension that reads each column of the gravity-applied grid from bottom to top.
Visual walkthrough
Let's trace through a 3x3 box step by step. Watch how gravity slides stones rightward, then rotation rearranges everything.
Step 1: Original box.
The input grid. Stones (#) are affected by gravity. Obstacles (*) block movement. Empty cells (.) are open space.
Step 2: Apply gravity. Stones fall right within each row, stopped by obstacles.
Process each row right to left. Stones slide to the rightmost available empty cell. In row 2, the stone stops at column 1 because the obstacle at column 2 blocks it.
Step 3: Rotate 90 degrees clockwise. Read each column bottom-to-top to form the new rows.
The first column (top to bottom: '.', '.', '.') becomes the first row reversed. The grid dimensions stay 3x3 here, but for non-square grids an m x n box becomes n x m.
The gravity step is the core of the problem. Once stones are in their correct positions within each row, the rotation is a mechanical transformation that you can write from the formula alone.
Complexity analysis
| Metric | Value |
|---|---|
| Time | O(m * n) |
| Space | O(m * n) |
Time: The gravity simulation visits each cell once per row, so it is O(m * n). The rotation also visits each cell once to build the new matrix. Total: O(m * n).
Space: The rotated matrix is n x m, which takes O(m * n) space. The gravity step is done in place on the original grid, so it adds no extra space beyond the output.
The building blocks
This problem is built on two reusable pieces that CodeBricks drills independently:
Two-pointer gravity simulation
The pattern of using a write pointer to compact elements toward one end of an array, skipping over barriers:
empty = n - 1
for col in range(n - 1, -1, -1):
if row[col] == "*":
empty = col - 1
elif row[col] == "#":
row[col] = "."
row[empty] = "#"
empty -= 1
This is a variation of the "move zeroes" or "partition array" pattern. You have a read pointer (col) that scans the array and a write pointer (empty) that tracks where the next element should go. Obstacles act as partition boundaries that reset the write pointer.
You will see this same two-pointer compaction in problems like Move Zeroes (LeetCode 283), Sort Colors (LeetCode 75), and Remove Duplicates (LeetCode 26). The common thread: one pointer reads, one pointer writes, and certain elements act as barriers or delimiters.
90-degree clockwise matrix rotation
The transformation that maps (r, c) to (c, m - 1 - r):
rotated = [[box[m - 1 - r][c] for r in range(m)] for c in range(n)]
For square matrices, this can be done in place using transpose + reverse. For non-square matrices (like this problem), you need to allocate a new grid because the dimensions change from m x n to n x m. Either way, the index mapping is the same.
Edge cases
- No stones: the grid is all obstacles and empty cells. Gravity does nothing, and the rotation just transposes the grid structure. The output is correct with no special handling.
- No obstacles: stones in each row all slide to the rightmost positions. After rotation, they stack at the bottom of each column.
- Single row:
[["#", ".", "#", "*", "."]]becomes a single column after rotation. Gravity slides stones right within that row first. - Single column:
[["#"], ["."], ["*"]]becomes a single row after rotation. Each "row" in the original has only one cell, so gravity has no effect. - All stones: every cell is
'#'. Gravity does not move anything. Rotation still changes the grid dimensions. - Stones already settled: if stones are already at the rightmost positions (or packed against obstacles), gravity is a no-op and the output is just the rotated grid.
From understanding to recall
You now understand the two-step approach: gravity first, rotate second. The gravity simulation is a two-pointer scan. The rotation is an index formula. Both are patterns you will use in other problems.
But under interview pressure, the details matter. Which direction do you scan for gravity? What does the empty pointer reset to when you hit an obstacle? What is the exact index mapping for clockwise rotation?
Spaced repetition locks these details in. You write the gravity loop and the rotation formula from scratch. You do it today, again in two days, again in five. After a few reps, you see "rotating the box" and the two-step decomposition appears on your screen without hesitation. No fumbling with index math, no confusing rows with columns.
The two-pointer gravity simulation and matrix rotation are two of roughly 60 reusable building blocks that cover hundreds of LeetCode problems. Learning these individually and drilling them with spaced repetition is far more effective than grinding random problems and hoping the patterns stick.
Related posts
- Rotate Image - In-place 90-degree rotation of a square matrix using transpose + reverse, the same rotation concept applied to the in-place case
- Spiral Matrix - Layer-by-layer matrix traversal that tests similar index-management skills
- Set Matrix Zeroes - Another in-place matrix problem where you process row and column information independently
CodeBricks breaks Rotating the Box into its gravity-simulation and matrix-rotation building blocks, then drills them independently with spaced repetition. You type the two-pointer compaction loop and the rotation formula from scratch until the pattern is automatic. When a matrix transformation problem shows up in your interview, you do not think about it. You just write it.