1861. Rotating the Box

Array
Two Pointers
Matrix
Simulation

TIME

O(m × n)

SPACE

O(m × n)

Intuition

After the box rotates clockwise, stones fall downward. In the original orientation, that is equivalent to stones sliding to the right within each row until blocked by an obstacle or another stone.

So we can first settle stones in each row from right to left, then rotate the settled box.

Approach

For each row, set empty to the rightmost column.
Scan the row from right to left.
If an obstacle '*' is found:
- stones cannot cross it
- reset empty to the cell immediately left of the obstacle
If a stone '#' is found:
- move it to empty
- mark the original cell as empty if it moved
- decrement empty
After gravity is simulated in all rows, rotate the matrix clockwise:
- original (row, col) moves to (col, m - 1 - row)

Complexity

Time: O(m × n), each cell is processed a constant number of times
Space: O(m × n), required for the returned rotated matrix

Edge Cases

Single row or single column
Rows with no stones
Rows with only obstacles
Obstacles splitting a row into independent gravity segments

Code

from typing import List


class Solution:
    def rotateTheBox(self, boxGrid: List[List[str]]) -> List[List[str]]:
        """
        1861. Rotating the Box
        Time: O(m × n)
        Space: O(m × n)
        """
        m, n = len(boxGrid), len(boxGrid[0])

        for row in range(m):
            empty = n - 1

            for col in range(n - 1, -1, -1):
                if boxGrid[row][col] == "*":
                    empty = col - 1
                elif boxGrid[row][col] == "#":
                    boxGrid[row][col] = "."
                    boxGrid[row][empty] = "#"
                    empty -= 1

        rotated = [["."] * m for _ in range(n)]

        for row in range(m):
            for col in range(n):
                rotated[col][m - 1 - row] = boxGrid[row][col]

        return rotated

/**
 * 1861. Rotating the Box
 * Time: O(m × n)
 * Space: O(m × n)
 */
class Solution {
    public char[][] rotateTheBox(char[][] boxGrid) {
        int m = boxGrid.length;
        int n = boxGrid[0].length;

        for (int row = 0; row < m; row++) {
            int empty = n - 1;

            for (int col = n - 1; col >= 0; col--) {
                if (boxGrid[row][col] == '*') {
                    empty = col - 1;
                } else if (boxGrid[row][col] == '#') {
                    boxGrid[row][col] = '.';
                    boxGrid[row][empty] = '#';
                    empty--;
                }
            }
        }

        char[][] rotated = new char[n][m];

        for (int row = 0; row < m; row++) {
            for (int col = 0; col < n; col++) {
                rotated[col][m - 1 - row] = boxGrid[row][col];
            }
        }

        return rotated;
    }
}