364. Rotating the Box

Rotating the box clockwise turns each row into a column. Stones fall to the right within each row (because right becomes down after rotation). So we can simulate gravity in the original orientation, then rotate.

Approach

1. For each row in boxGrid, slide stones to the right within their obstacle-bounded segments:
   • Walk right-to-left with a write pointer wp initialised to the column index.
   • On '#': move it to wp, decrement wp.
   • On '*': reset wp to the cell just to the left of the obstacle.
   • On '.': skip.
2. Rotate the result 90° clockwise: cell (i, j) of the input becomes cell (j, m - 1 - i) of the output.

Complexity

• Time: O(m · n) — each cell visited a constant number of times.
• Space: O(m · n) — the rotated output grid.

import java.util.*;

class Solution {
    public char[][] rotateTheBox(char[][] box) {
        int m = box.length, n = box[0].length;
        // Apply gravity: stones fall to the right
        for (int i = 0; i < m; i++) {
            int wp = n - 1;
            for (int j = n - 1; j >= 0; j--) {
                if (box[i][j] == '*') {
                    wp = j - 1;
                } else if (box[i][j] == '#') {
                    box[i][j] = '.';
                    box[i][wp] = '#';
                    wp--;
                }
            }
        }
        // Rotate 90 degrees clockwise
        char[][] rotated = new char[n][m];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                rotated[j][m - 1 - i] = box[i][j];
            }
        }
        return rotated;
    }
}

After rotation, what was the right edge of each row becomes the bottom of each column — so gravity in the rotated box pulls stones in that direction. Solve it in the original orientation by sliding stones rightward, then rotate as a final step.

Why we sweep right-to-left in each row

The box rotates 90° clockwise. A row in the original becomes a column in the result, and the rightmost cell of the row becomes the bottom of the column. So when gravity acts in the rotated box, stones in each row of the original should fall to the right — until they hit an obstacle, another stone, or the right wall.

So Step 1: simulate gravity on each row, in place. Step 2: rotate.

Simulating gravity in one row

Walk the row right-to-left. Keep a pointer empty = the rightmost free slot in the current segment (a segment is a stretch of cells between two obstacles, or between an obstacle and a wall).

• row[j] == '.': empty cell, do nothing.
• row[j] == '#': there's a stone here that wants to fall right. Move it to empty, then decrement empty to the next free slot leftward.
• row[j] == '*': an obstacle. Stones to its left can't fall past it — start a new segment. Set empty = j - 1.

Walk-through

Row [#, ., *, ., #], n = 5, start empty = 4.

After gravity: [., #, *, ., #]. Notice the stone left of the obstacle stopped at column 1, and the stones right of it stayed at column 4 (already at the wall).

Rotating clockwise

After all rows have settled, rotate the m × n box into an n × m result. The cell at (i, j) of the original maps to (j, m - 1 - i) of the rotated box. A cleaner way to write it: row j of the result is [box[m-1][j], box[m-2][j], …, box[0][j]].

End-to-end example

Input:

[ . , # , # , . , . , # ,
  # , # , # , * , . , . ,
  # , # , # , . , # , .  ]   ← three rows of 6 chars each

After per-row gravity (each row's stones slide right):

[ . , . , . , # , # , # ,
  # , # , # , * , . , . ,    ← obstacle splits the row, stones on each side fall right
  . , . , # , # , # , #  ]

Rotate 90° clockwise → n = 6 rows of m = 3 chars (omitted for brevity; you can verify column-by-column).

Edge cases

• Row of all '.': untouched.
• Row entirely blocked by obstacles: stones can't move past them; sweep handles this naturally because empty keeps resetting.

Complexity

• Time: O(m · n) — each cell is read once during gravity and once during rotation.
• Space: O(m · n) — for the rotated output.