Problem Description

You have a box represented as an m x n matrix called boxGrid, where each cell contains one of three possible characters:

• '#' represents a stone
• '*' represents a stationary obstacle that cannot move
• '.' represents an empty space

The problem asks you to simulate what happens when this box is rotated 90 degrees clockwise. When the box rotates, two things happen:

1. The entire matrix rotates 90 degrees clockwise - This means the rightmost column becomes the top row, the leftmost column becomes the bottom row, etc.

2. Stones fall due to gravity - After rotation, gravity causes stones to fall downward in their new orientation. Each stone will fall until it hits:

   • An obstacle ('*')
   • Another stone ('#')
   • The bottom of the box

Important constraints:

• Obstacles ('*') remain fixed in their positions and don't fall
• Stones only fall vertically downward in the rotated box (they don't move horizontally)
• Initially, all stones are guaranteed to be resting on something (not floating)

The task is to return the final state of the box as an n x m matrix (note the dimensions are swapped due to the 90-degree rotation) showing where all stones end up after the rotation and falling process is complete.

For example, if you have a stone above an empty space in the rotated box, it will fall through the empty space until it hits an obstacle, another stone, or reaches the bottom. The simulation needs to handle multiple stones in the same column falling and stacking on top of each other correctly.

Intuition

The problem can be broken down into two independent operations: rotating the matrix and simulating gravity.

For the rotation part, we need to understand how a 90-degree clockwise rotation transforms coordinates. When rotating a matrix clockwise, the element at position (i, j) in the original matrix moves to position (j, m-1-i) in the rotated matrix, where m is the number of rows. This is a standard matrix transformation - the row index becomes the column index, and the column index determines the new row position from the bottom.

For simulating gravity, we need to think about how stones fall in each column of the rotated matrix. The key insight is that we can process each column independently from bottom to top. As we scan upward in a column, we need to track where stones can potentially fall to.

Using a queue to track empty positions is clever because:

• When we encounter an empty space '.', we add its position to our queue of available spots
• When we encounter a stone '#', if there are empty spots below it (in our queue), the stone should fall to the lowest available spot
• When we encounter an obstacle '*', it blocks everything above it from falling past that point, so we clear our queue

Processing from bottom to top ensures that we fill the lowest positions first, naturally simulating how multiple stones would stack on top of each other. The queue automatically maintains the order of available empty positions from bottom to top, making it easy to always place falling stones in the correct spot.

The beauty of this approach is that it separates the geometric transformation (rotation) from the physics simulation (gravity), making each part simpler to implement and understand.

Learn more about Two Pointers patterns.

Solution Approach

The solution implements the two-phase approach: first rotating the matrix, then simulating gravity.

Phase 1: Matrix Rotation (90 degrees clockwise)

We create a new matrix ans with dimensions n x m (swapped from the original m x n). For each element at position (i, j) in the original matrix, we place it at position (j, m-1-i) in the rotated matrix:

ans = [[None] * m for _ in range(n)]
for i in range(m):
    for j in range(n):
        ans[j][m - i - 1] = box[i][j]

This transformation ensures that:

• The first row becomes the last column
• The last row becomes the first column
• Elements rotate 90 degrees clockwise

Phase 2: Simulating Gravity with Queue

After rotation, we process each column independently to simulate stones falling:

for j in range(m):  # For each column
    q = deque()     # Queue to track empty positions
    for i in range(n - 1, -1, -1):  # Scan from bottom to top

For each position in the column (scanning upward), we handle three cases:

1. Obstacle '*': Clear the queue since stones above cannot fall past this point

   if ans[i][j] == '*':
       q.clear()

2. Empty space '.': Add this position to the queue as a potential landing spot

   elif ans[i][j] == '.':
       q.append(i)

3. Stone '#': If empty spaces exist below (queue not empty), move the stone to the lowest available position

   elif q:
       ans[q.popleft()][j] = '#'  # Place stone at lowest empty spot
       ans[i][j] = '.'             # Current position becomes empty
       q.append(i)                 # Add current position as new empty spot

The queue (deque) is used efficiently here:

• popleft() always gives us the lowest (earliest added) empty position
• append() adds newly emptied positions to the back
• This maintains the bottom-to-top order of available positions

The algorithm correctly handles multiple stones falling in sequence because when a stone falls from position i, that position becomes empty and is added back to the queue, allowing stones above to potentially fall into it.

After processing all columns, ans contains the final state of the box after rotation and gravity simulation.

Example Walkthrough

Let's work through a small example to illustrate the solution approach.

Initial Box (3x3):

# . *
# # .
. . .

Step 1: Rotate 90 degrees clockwise

Using the transformation formula (i,j) → (j, m-1-i) where m=3:

• (0,0)='#' → (0,2)='#'
• (0,1)='.' → (1,2)='.'
• (0,2)='*' → (2,2)='*'
• (1,0)='#' → (0,1)='#'
• (1,1)='#' → (1,1)='#'
• (1,2)='.' → (2,1)='.'
• (2,0)='.' → (0,0)='.'
• (2,1)='.' → (1,0)='.'
• (2,2)='.' → (2,0)='.'

After rotation:

. # #
. # .
. . *

Step 2: Apply gravity column by column

Column 0: Process from bottom to top (indices 2→1→0)

• i=2: '.' - add to queue: q=[2]
• i=1: '.' - add to queue: q=[2,1]
• i=0: '.' - add to queue: q=[2,1,0]
• Final column 0: ['.', '.', '.'] (no stones to fall)

Column 1: Process from bottom to top

• i=2: '.' - add to queue: q=[2]
• i=1: '#' - stone with empty space below!
  • Place stone at q.popleft()=2: position (2,1) becomes '#'
  • Current position (1,1) becomes '.'
  • Add position 1 to queue: q=[1]
• i=0: '#' - stone with empty space below!
  • Place stone at q.popleft()=1: position (1,1) becomes '#'
  • Current position (0,1) becomes '.'
  • Add position 0 to queue: q=[0]
• Final column 1: ['.', '#', '#']

Column 2: Process from bottom to top

• i=2: '*' - obstacle, clear queue: q=[]
• i=1: '.' - add to queue: q=[1]
• i=0: '#' - stone with empty space below!
  • Place stone at q.popleft()=1: position (1,2) becomes '#'
  • Current position (0,2) becomes '.'
  • Add position 0 to queue: q=[0]
• Final column 2: ['.', '#', '*']

Final Result:

. . .
. # #
. # *

The stones that were originally in the top-left and middle of the box have fallen to rest on the bottom row and the obstacle after rotation.

Solution Implementation

Time and Space Complexity

Time Complexity: O(m × n)

The algorithm consists of two main phases:

1. Matrix rotation phase: The nested loops iterate through all m × n elements of the original box to create the rotated matrix. Each element is accessed and assigned exactly once, resulting in O(m × n) operations.

2. Gravity simulation phase: After rotation, the algorithm processes the rotated matrix (which has dimensions n × m). For each column j (total m columns), it iterates through all rows i (total n rows). Although there are deque operations (append, popleft, clear), each cell is visited once, and the deque operations are O(1) amortized. The total operations remain O(n × m) = O(m × n).

Since both phases are O(m × n) and execute sequentially, the overall time complexity is O(m × n) + O(m × n) = O(m × n).

Space Complexity: O(m × n)

The algorithm allocates a new 2D array ans with dimensions n × m to store the rotated box. This requires O(n × m) = O(m × n) space. The deque q uses at most O(n) space in the worst case (when a column contains all empty cells), but this is dominated by the space used for the ans matrix. Therefore, the total space complexity is O(m × n).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Incorrect Rotation Mapping

Issue: One of the most common mistakes is getting the rotation transformation wrong. Many developers incorrectly map (i, j) to (j, i) or (n-1-j, i), which doesn't produce a proper 90-degree clockwise rotation.

Why it happens: The formula for 90-degree clockwise rotation isn't intuitive, and it's easy to confuse with transpose or other transformations.

Solution: Remember that for 90-degree clockwise rotation from an m×n matrix to an n×m matrix, the correct mapping is:

• Original position (i, j) → Rotated position (j, m-1-i)
• Verify with a simple example: the top-left corner (0, 0) should map to the top-right (0, m-1)

Pitfall 2: Processing Gravity in Wrong Direction

Issue: Processing stones from top to bottom instead of bottom to top when simulating gravity, leading to incorrect stone positions.

Why it happens: It seems logical to process from top since stones fall down, but this approach makes it difficult to determine where each stone should land.

Solution: Always process from bottom to top when simulating gravity:

for row in range(cols - 1, -1, -1):  # Bottom to top

This way, you know exactly which positions are available for falling stones before encountering them.

Pitfall 3: Not Maintaining Order of Empty Positions

Issue: Using a stack (LIFO) instead of a queue (FIFO) for tracking empty positions, causing stones to fall to incorrect positions.

Why it happens: Both data structures seem reasonable for tracking positions, but they produce different results.

Solution: Use a deque with popleft() to ensure stones fall to the lowest available position:

empty_positions = deque()
lowest_empty = empty_positions.popleft()  # Gets the earliest (lowest) position

Pitfall 4: Forgetting to Clear Queue at Obstacles

Issue: Not clearing the empty positions queue when encountering an obstacle, allowing stones to incorrectly "fall through" obstacles.

Why it happens: It's easy to focus on moving stones and forget that obstacles create barriers that reset the falling behavior.

Solution: Always clear the queue when hitting an obstacle:

if rotated_box[row][col] == '*':
    empty_positions.clear()

Pitfall 5: Dimension Confusion After Rotation

Issue: Using the wrong dimensions for the rotated matrix or incorrectly iterating through rows and columns after rotation.

Why it happens: After rotation, the dimensions swap (m×n becomes n×m), and it's easy to mix up which dimension is which.

Solution: Clearly define and use consistent variable names:

rows, cols = len(box), len(box[0])  # Original dimensions
rotated_box = [[None] * rows for _ in range(cols)]  # Swapped dimensions
# After rotation: iterate cols for rows, rows for columns
for col in range(rows):  # Each column in rotated box
    for row in range(cols - 1, -1, -1):  # Each row in that column