1861. Rotating the Box - Detailed Explanation

Problem Statement

You are given an m x n matrix (the “box”) where each cell is one of the following characters:

• '#' represents a stone.
• '*' represents an obstacle.
• '.' represents an empty space.

Initially, the box is in a horizontal position. Due to gravity, stones in the box will fall to the right (i.e. toward the “bottom” when the box is rotated) until they hit either an obstacle or the right wall. In other words, in the original orientation, each stone can slide as far right as possible within its row without passing through an obstacle.

After simulating this “gravity” effect in the original box, you must then rotate the box 90 degrees clockwise and return the resulting box.

Examples

Example 1

Input:

box = [
  ["#", ".", "*", "."],
  ["#", "#", "*", "."],
  [".", "#", ".", "."]
]

Processing (Step 1: Simulate Gravity):

• Row 0:
  Original: ["#", ".", "*", "."]
  Process from right to left:

  • Start with a pointer at the far right (index 3).
  • At index 2, there is an obstacle '*' → update pointer to index 1 (just left of the obstacle).
  • At index 0, there is a stone '#' → move it to the farthest available position (index 1).
    After processing, Row 0 becomes: [".", "#", "*", "."].

• Row 1:
  Original: ["#", "#", "*", "."]
  Process similarly (pointer starts at index 3, reset when hitting obstacle at index 2):

  • Both stones can “fall” as far right as possible within the segment.
    Row 1 remains: ["#", "#", "*", "."].

• Row 2:
  Original: [".", "#", ".", "."]
  Process from right to left (pointer starts at index 3):

  • At index 1, stone '#' falls to index 3.
    Row 2 becomes: [".", ".", ".", "#"].

After gravity simulation, the box becomes:

[
  [".", "#", "*", "."],
  ["#", "#", "*", "."],
  [".", ".", ".", "#"]
]

Processing (Step 2: Rotate 90° Clockwise):

The rotated box will have dimensions n x m. For each cell in the rotated box:

• The element at position new_box[i][j] is taken from box[m - 1 - j][i].

For our example:

• New Row 0: Formed by taking column 0 from bottom to top:
  • From Row 2: '.'
  • From Row 1: '#'
  • From Row 0: "."
    → New Row 0: [".", "#", "."]
• New Row 1: Column 1 from bottom to top:
  • From Row 2: "."
  • From Row 1: '#'
  • From Row 0: "#"
    → New Row 1: [".", "#", "#"]
• New Row 2: Column 2 from bottom to top:
  • From Row 2: "."
  • From Row 1: "*"
  • From Row 0: "*"
    → New Row 2: [".", "*", "*"]
• New Row 3: Column 3 from bottom to top:
  • From Row 2: "#"
  • From Row 1: "."
  • From Row 0: "."
    → New Row 3: ["#", ".", "."]

Output:

[
  [".", "#", "."],
  [".", "#", "#"],
  [".", "*", "*"],
  ["#", ".", "."]
]

Hints

1. Simulating Gravity:
   In the original box, stones move rightward (as if “falling”) until they reach either an obstacle ('*') or the end of the row. Process each row individually, scanning from right to left and maintaining a pointer where the next stone should “fall.”

2. Rotation:
   Rotating the box 90° clockwise can be done by creating a new matrix of size n x m and using the transformation:

   new_box[i][j] = box[m - 1 - j][i]
   

3. Separate Concerns:
   It’s easier to first simulate gravity on the original box and then perform the rotation rather than trying to simulate both at once.

Approaches

Approach 1: Two-Step Simulation

1. Simulate Gravity (Per Row):
   • For each row, iterate from rightmost index to leftmost.
   • Use a pointer initialized to the last column. When you encounter an obstacle ('*'), reset the pointer to just left of the obstacle.
   • If you see a stone ('#'), move it to the pointer’s location (if it’s not already there) and decrement the pointer.
   • Replace cells where stones have moved from with '.'.
2. Rotate the Box 90° Clockwise:
   • Create a new matrix with dimensions n x m.
   • For each cell in the new matrix, assign:

     new_box[i][j] = box[m - 1 - j][i]
     

Pros:

• Clear separation of simulation and rotation.

Cons:

• Requires two passes (one per row for gravity and one for rotation).

Approach 2: In-Place Simulation with Extra Space for Rotation

• You may perform the simulation as above and then use an extra matrix for the rotated result. This approach is simpler to implement correctly.

Step-by-Step Walkthrough with Visual Example

Consider the following box:

box = [
  ["#", ".", "*", "."],
  ["#", "#", "*", "."],
  [".", "#", ".", "."]
]

Step 1: Simulate Gravity on Each Row

• Row 0 ("#", ".", "*", "."):

  • Initialize pointer at index 3.
  • Index 3: '.' → do nothing.
  • Index 2: '*' → set pointer = 1.
  • Index 1: '.' → do nothing.
  • Index 0: '#' → move stone to index 1 (set cell 0 to '.' and cell 1 to '#').
  • Final Row 0: [".", "#", "*", "."]

• Row 1 ("#", "#", "*", "."):

  • Pointer = 3.
  • Index 3: '.' → do nothing.
  • Index 2: '*' → set pointer = 1.
  • Index 1: '#' → stone already at pointer 1; update pointer to 0.
  • Index 0: '#' → move stone to pointer 0.
  • Final Row 1 remains: ["#", "#", "*", "."]

• Row 2 (".", "#", ".", "."):

  • Pointer = 3.
  • Index 3: '.' → do nothing.
  • Index 2: '.' → do nothing.
  • Index 1: '#' → move stone to pointer 3; set index 1 to '.', index 3 to '#'; update pointer to 2.
  • Index 0: '.' → do nothing.
  • Final Row 2: [".", ".", ".", "#"]

After simulation, the box becomes:

[
  [".", "#", "*", "."],
  ["#", "#", "*", "."],
  [".", ".", ".", "#"]
]

Step 2: Rotate the Box 90° Clockwise

Create a new matrix of dimensions 4 x 3 (since original is 3 x 4).

• New Row 0:
  From original column 0 (bottom to top):
  Row 2, col 0: "."
  Row 1, col 0: "#"
  Row 0, col 0: "."
  → New Row 0: [".", "#", "."]

• New Row 1:
  From original column 1 (bottom to top):
  Row 2, col 1: "."
  Row 1, col 1: "#"
  Row 0, col 1: "#"
  → New Row 1: [".", "#", "#"]

• New Row 2:
  From original column 2 (bottom to top):
  Row 2, col 2: "."
  Row 1, col 2: "*"
  Row 0, col 2: "*"
  → New Row 2: [".", "*", "*"]

• New Row 3:
  From original column 3 (bottom to top):
  Row 2, col 3: "#"
  Row 1, col 3: "."
  Row 0, col 3: "."
  → New Row 3: ["#", ".", "."]

Final Output:

[
  [".", "#", "."],
  [".", "#", "#"],
  [".", "*", "*"],
  ["#", ".", "."]
]

Code Implementation

Python Code