Rotating the Box

Problem

We are given a grid that shows a box from the side.

Each cell can be:

• # for a stone
• * for a fixed obstacle
• . for empty space

The box is rotated 90 degrees clockwise. After that, gravity pulls every stone down until it hits the bottom, an obstacle, or another stone.

Return the final rotated grid.

Key Observation

A cell at original position (i, j) moves to this position after a clockwise rotation:

(j, m - i - 1)

where:

• m is the number of rows in the original box
• n is the number of columns in the original box

So the answer grid has size n x m.

The second observation is about gravity. In the original side-view, stones fall to the right after the box is rotated clockwise. That means we can process each original row from right to left and keep a pointer to the next place where a stone should land.

Approach

Instead of first rotating the whole grid and then applying gravity, we can do both together.

For every original row i:

1. Set lowestEmptyRow = n - 1
2. Scan columns j from right to left
3. If box[i][j] is a stone:
   • place it at result[lowestEmptyRow][m - i - 1]
   • move lowestEmptyRow one row up
4. If box[i][j] is an obstacle:
   • place it at result[j][m - i - 1]
   • reset lowestEmptyRow = j - 1
5. If box[i][j] is empty, do nothing

The answer starts filled with .. That lets empty cells stay empty automatically.

class Solution {
    public char[][] rotateTheBox(char[][] box) {
        int m = box.length;
        int n = box[0].length;
        char[][] result = new char[n][m];

        for (int r = 0; r < n; r++) {
            for (int c = 0; c < m; c++) {
                result[r][c] = '.';
            }
        }

        for (int i = 0; i < m; i++) {
            int lowestEmptyRow = n - 1;

            for (int j = n - 1; j >= 0; j--) {
                if (box[i][j] == '#') {
                    result[lowestEmptyRow][m - i - 1] = '#';
                    lowestEmptyRow--;
                } else if (box[i][j] == '*') {
                    result[j][m - i - 1] = '*';
                    lowestEmptyRow = j - 1;
                }
            }
        }

        return result;
    }
}

Dry Run

Take:

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

Here m = 2 and n = 4, so the result will be 4 x 2.

Process row 0: ["#",".","*","."]

• start with lowestEmptyRow = 3
• j = 3 is ., so skip it
• j = 2 is *, place it at result[2][1], then set lowestEmptyRow = 1
• j = 1 is ., so skip it
• j = 0 is #, place it at result[1][1]

Process row 1: ["#","#","*","."]

• start with lowestEmptyRow = 3
• j = 3 is ., so skip it
• j = 2 is *, place it at result[2][0], then set lowestEmptyRow = 1
• j = 1 is #, place it at result[1][0]
• j = 0 is #, place it at result[0][0]

Final result:

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

Why This Works

After rotation, each original row becomes one column in the final grid.

Inside that column, obstacles stay at their rotated positions. Stones only move downward until blocked. When we scan the original row from right to left, lowestEmptyRow always points to the lowest available spot in the current obstacle-separated segment.

When we see:

• a stone, it must fall to lowestEmptyRow
• an obstacle, no stone can pass through it, so the next available spot becomes the cell above the obstacle
• an empty cell, it contributes nothing because the result is already filled with .

This simulates gravity without a second pass.

Complexity Analysis

Time Complexity: O(m * n)

We visit every cell once.

Space Complexity: O(m * n)

The returned rotated grid has n * m cells.

Common Mistakes

1. Rotating first, then searching upward for each empty cell

That can become O(m * n^2) because each empty cell may scan many cells above it.

2. Resetting the pointer incorrectly after an obstacle

If an obstacle is at original column j, then the next stone in that segment can only land at j - 1, so use:

lowestEmptyRow = j - 1

3. Writing stones to their direct rotated position

The direct rotated position is only correct for obstacles. Stones must use the gravity pointer because they may fall before reaching the final answer.

Use the tabs below to switch between Java, C++, JavaScript, TypeScript, C, C#, Go, and Rust implementations.