1861. Rotating the Box - Detailed Explanation

Problem Statement

You are given an m x n matrix called box where each cell is one of:

• '#' — a stone,
• '*' — an obstacle, or
• '.' — an empty space.

Rules:

1. Gravity Simulation:
   In the original box, gravity causes the stones to slide to the right. In each row, a stone will keep moving right until it either reaches the right end, meets an obstacle, or bumps into another stone that has already come to rest.
2. Rotation:
   After simulating gravity in the box, rotate the entire box 90° clockwise. In the rotated box, gravity is “downward.”

Your goal: Return the final state of the rotated box.

Example 1

• Input:

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

• Output:

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

• Explanation:
  1. Simulate Gravity (in the original box):
     • Row 0:
       • Original: ["#", ".", "*", "."]
       • Process from right to left:
         • Start with pointer at index 3.
         • At index 3: '.' remains empty.
         • At index 2: '*' is an obstacle → reset pointer to index 1.
         • At index 1: '.' is empty.
         • At index 0: '#' is a stone → move it to pointer index 1.
       • Row 0 becomes: [".", "#", "*", "."]
     • Row 1:
       • Original: ["#", "#", "*", "."]
       • Process similarly (with an obstacle at index 2, the stones in indices 0 and 1 are already as right as possible) → remains unchanged.
     • Row 2:
       • Original: ["#", "#", "#", "."]
       • Process from right:
         • Pointer starts at index 3.
         • Index 3: '.' remains empty.
         • Index 2: '#' moves to index 3, pointer becomes 2.
         • Index 1: '#' moves to index 2, pointer becomes 1.
         • Index 0: '#' moves to index 1, pointer becomes 0.
       • Row 2 becomes: [".", "#", "#", "#"]
  2. Rotate the Box 90° Clockwise:
     The new dimensions become n x m (4 x 3). The rotated box is built by taking, for each new cell at position (r, c), the value from the original cell at position (m - 1 - c, r).
     The final rotated box is:

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

Example 2

• Input:

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

• Output:

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

• Explanation:
  • Simulate Gravity:
    • Row 0: Stone slides to the right if possible (here it is already at index 0 with an obstacle blocking further right movement in its segment).
    • Row 1: Remains as is since the stone cannot move past the obstacle.
  • Rotate Clockwise:
    The resulting rotated box is built from the transformed rows.

Example 3

• Input:

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

• Output:

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

• Explanation:
  • There is only one stone in row 0 and the obstacles in row 1 block movement. After rotation, the stone falls into the correct new position, and the obstacles remain in place.

Constraints:

• 1 ≤ m, n ≤ 500 (approximately)
• Each element in the box is either '#', '*', or '.'.

Hints

• Hint 1:
  Process each row individually and simulate gravity by scanning from right to left. Use a pointer to mark where the next stone should “land” within a segment (i.e., the area between an obstacle or the row’s edge).

• Hint 2:
  When you encounter an obstacle ('*'), reset the pointer to just before the obstacle because stones cannot cross it.

• Hint 3:
  Once the gravity simulation is complete, remember that rotating the matrix 90° clockwise means the new cell at (r, c) corresponds to the original cell at (m - 1 - c, r).

Approach 1: Simulate Gravity Then Rotate (Optimal)

Idea

1. Simulate Gravity in the Original Box:

   • For each row, start from the rightmost column and move left.

   • Use a pointer (initially set to the last column index) to indicate the “landing spot” for stones.

   • When a stone ('#') is encountered, remove it from its current position (set it to empty) and place it at the pointer position; then move the pointer one step to the left.

   • When an obstacle ('*') is encountered, reset the pointer to just left of the obstacle.

2. Rotate the Box 90° Clockwise:

   • Create a new matrix with dimensions n x m.
   • For every new cell (r, c), assign it the value of the original cell at (m - 1 - c, r).

Visual Walkthrough

Consider the following row from the original box:

Row: ["#", ".", "*", "."]

• Step 1: Gravity Simulation in the Row

  • Set pointer = 3 (rightmost index).
  • Start at index 3: '.' (empty) → do nothing.
  • Index 2: '*' (obstacle) → reset pointer = index 1.
  • Index 1: '.' (empty) → do nothing.
  • Index 0: '#' (stone) → move the stone to the pointer (index 1), then set index 0 to '.'.
  • Resulting row becomes:

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

• Step 2: Rotate the Entire Box

  • After processing all rows, build the rotated matrix using the rule:
    new[r][c] = old[m - 1 - c][r].
  • This operation “flips” the rows and columns so that the simulated gravity (to the right) becomes gravity downward in the new orientation.

Code Implementation

Python Code