Naive Solution

The naive approach involves first rotating the box 90 degrees clockwise and then simulating the falling of the stones. Rotating the box can be done by creating a new matrix and filling it with the appropriate values from the original matrix. Simulating the falling of the stones involves iterating through each column from bottom to top. If we encounter a stone, we move it down as far as it can go until it hits an obstacle, another stone, or the bottom of the box.

Code

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

        // Rotate the box
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                rotatedBox[j][m - 1 - i] = box[i][j];
            }
        }

        // Simulate the falling of stones
        for (int j = 0; j < n; j++) {
            for (int i = m - 1; i >= 0; i--) {
                if (rotatedBox[j][i] == '#') {
                    int k = i + 1;
                    while (k < m && rotatedBox[j][k] == '.') {
                        k++;
                    }
                    rotatedBox[j][i] = '.';
                    rotatedBox[j][k - 1] = '#';
                }
            }
        }

        return rotatedBox;
    }
}

Big(O) Runtime

• Rotating the box takes O(m * n) time.
• Simulating the falling of stones takes O(m * n * m) in the worst case (each stone might need to fall all the way to the bottom in each column).

Therefore, the overall runtime is O(m * n * m).

Big(O) Space usage

• The rotated box requires O(m * n) space. The simulation is done in place.

Thus, the overall space usage is O(m * n).

Optimal Solution

The optimal solution reduces the time complexity of simulating the falling of the stones. Instead of moving one stone at a time, we can count the number of stones between obstacles. Then, fill the section with the appropriate number of stones and empty cells.

Code

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

        // Rotate the box
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                rotatedBox[j][m - 1 - i] = box[i][j];
            }
        }

        // Simulate the falling of stones
        for (int j = 0; j < n; j++) {
            int lastObstacle = m;
            int stoneCount = 0;
            for (int i = m - 1; i >= -1; i--) {
                if (i == -1 || rotatedBox[j][i] == '*') {
                    // Fill the section with stones and empty cells
                    for (int k = i + 1; k < lastObstacle; k++) {
                        if (stoneCount > 0) {
                            rotatedBox[j][k] = '#';
                            stoneCount--;
                        } else {
                            rotatedBox[j][k] = '.';
                        }
                    }
                    if (i != -1) {
                        rotatedBox[j][i] = '*'; // Keep the obstacle
                    }
                    lastObstacle = i;
                } else if (rotatedBox[j][i] == '#') {
                    stoneCount++;
                    rotatedBox[j][i] = '.'; // Clear the original stone position
                }
            }
        }

        return rotatedBox;
    }
}

Big(O) Runtime

• Rotating the box takes O(m * n) time.
• Simulating the falling of stones takes O(m * n) time.

Therefore, the overall runtime is O(m * n).

Big(O) Space usage

• The rotated box requires O(m * n) space.

Thus, the overall space usage is O(m * n).

Edge Cases

• Empty box: If the input box is empty (m = 0 or n = 0), return an empty box.
• Box with no stones: If the input box has no stones, return the rotated box with all empty cells.
• Box with no obstacles: If the input box has no obstacles, all stones should fall to the bottom.
• Box with only obstacles: If the input box has only obstacles, return the rotated box with the same obstacle positions.