Rotating the Box

How it works

We can combine the gravity simulation and rotation into a single pass. Instead of modifying the original grid and then rotating, we directly write stones and obstacles to their final positions in the rotated result grid. This eliminates the need to modify the input and performs both operations simultaneously.

Steps

1. Create a result grid of size COLS x ROWS, filled with empty cells ..
2. For each row in the original grid, initialize pointer i to COLS - 1.
3. Iterate from right to left:
   • If the cell is a stone #, place it at the rotated position corresponding to i, then decrement i.
   • If the cell is an obstacle *, place it at its rotated position and reset i to c - 1.
4. The rotated position for original (r, c) is (c, ROWS - r - 1) for obstacles, and (i, ROWS - r - 1) for stones.
5. Return the result grid.

Complexity

• Time complexity: O(m * n)
• Space complexity: O(m * n)

Where m is the number of rows and n is the number of columns.

Things to watch for

Applying Gravity in the Wrong Direction

After rotation, gravity pulls stones downward, but before rotation stones should fall to the right (toward higher column indices). Processing stones left-to-right instead of right-to-left causes stones to fall incorrectly, as earlier stones block the path for later ones.

Forgetting to Reset the Drop Position After Obstacles

When an obstacle * is encountered, the drop position pointer must reset to just before the obstacle (c - 1). Failing to reset this pointer causes stones to incorrectly pass through or stack on top of obstacles.

Incorrect Rotation Index Mapping

The rotation transforms position (r, c) to (c, ROWS - 1 - r) for a 90-degree clockwise rotation. Using incorrect formulas like (c, r) or (ROWS - 1 - r, c) results in a transposed or incorrectly flipped matrix instead of a proper rotation.

from typing import List

class Solution:
    def rotateTheBox(self, boxGrid: List[List[str]]) -> List[List[str]]:
        ROWS, COLS = len(boxGrid), len(boxGrid[0])

        res = [["."] * ROWS for _ in range(COLS)]

        for r in range(ROWS):
            i = COLS - 1
            for c in reversed(range(COLS)):
                if boxGrid[r][c] == "#":
                    res[i][ROWS - r - 1] = "#"
                    i -= 1
                elif boxGrid[r][c] == "*":
                    res[c][ROWS - r - 1] = "*"
                    i = c - 1

        return res

class Solution {
public:
    vector<vector<char>> rotateTheBox(vector<vector<char>>& boxGrid) {
        int ROWS = boxGrid.size(), COLS = boxGrid[0].size();
        vector<vector<char>> res(COLS, vector<char>(ROWS, '.'));
        for (int r = 0; r < ROWS; ++r) {
            int i = COLS - 1;
            for (int c = COLS - 1; c >= 0; --c) {
                if (boxGrid[r][c] == '#') {
                    res[i][ROWS - r - 1] = '#';
                    --i;
                } else if (boxGrid[r][c] == '*') {
                    res[c][ROWS - r - 1] = '*';
                    i = c - 1;
                }
            }
        }
        return res;
    }
};