Rotating the Box - Video Solutions

Problem Overview: You receive an m x n box represented as a matrix containing stones (#), obstacles (*), and empty spaces (.). Stones fall to the right due to gravity until blocked by an obstacle or another stone. After gravity settles, the entire box is rotated 90 degrees clockwise. The task is to return the final matrix.

Approach 1: Simulate Gravity and Then Rotate (Time: O(mn), Space: O(mn))

Process each row independently and simulate gravity before rotation. Scan from right to left using a pointer that marks the next position where a stone can settle. When you encounter a stone (#), move it to the pointer position and decrement the pointer. When an obstacle (*) appears, reset the pointer to the cell just left of the obstacle since stones cannot pass through it. After all rows stabilize, construct the rotated matrix by mapping box[r][c] to result[c][m-1-r]. This approach cleanly separates physics (gravity) from geometry (rotation) and is easy to reason about. It relies on sequential traversal of the array and basic matrix transformation.

Approach 2: Transpose and Simulate Gravity Directly (Time: O(mn), Space: O(mn))

Instead of settling stones first, rotate the matrix structure immediately and simulate gravity afterward. Build the rotated matrix using the same coordinate transform rotated[c][m-1-r] = box[r][c]. After rotation, gravity acts downward rather than to the right. Process each column using a two-pointer technique: scan upward while maintaining a pointer where the next falling stone should land. Obstacles reset the pointer just above them, while stones move down to the pointer location. This uses the classic two pointers pattern to compact stones within segments separated by obstacles.

Recommended for interviews: The gravity-first simulation is usually easier to explain and implement during interviews. You demonstrate understanding of constrained movement using pointers and then apply a standard matrix rotation. The transpose-first approach is equally optimal but slightly less intuitive because gravity changes direction after rotation. Showing either solution with clear reasoning and O(mn) complexity is typically what interviewers expect.