Problem Description

The "Rotating the Box" problem involves a 2D grid (the box) representing a box filled with stones, obstacles, and empty spaces. Each cell in the grid can contain:

• '#': a stone
• '*': an obstacle
• '.': an empty space

• Each stone can only move to the right, not through obstacles.
• After all stones have fallen, rotate the grid 90 degrees clockwise.
• There is always one valid solution for the given input.

Thought Process

The problem can be broken down into two main parts: simulating gravity for the stones, and rotating the box. Initially, one might think about rotating the box first and then simulating gravity, but that complicates the simulation due to changing directions. Instead, it's easier to let the stones "fall" to the right in the original grid, then perform the rotation.

The brute-force approach would be to check every cell for stones and try to move them right, but this can be slow and error-prone. By scanning each row from right to left, we can efficiently "collect" stones and place them as far right as possible, stopping at obstacles. Once all rows are processed, rotating the grid is a standard matrix manipulation.

Solution Approach

Here is a step-by-step breakdown of the algorithm:

1. Simulate Gravity:
   • For each row, process from right to left.
   • Keep track of the position where the next stone should fall (the write pointer).
   • If a stone ('#') is found, move it to the write position and decrement write.
   • If an obstacle ('*') is found, set write to just left of the obstacle.
   • Empty spaces ('.') are simply overwritten as stones "fall".
2. Rotate the Box:
   • After gravity simulation, create a new grid with swapped dimensions: the number of rows becomes the number of columns and vice versa.
   • For each cell in the original box, place its value in the rotated grid according to the 90-degree clockwise rotation rule: rotated[col][rows - row - 1] = box[row][col].
3. Return the Rotated Grid:
   • The rotated grid represents the final state of the box after all stones have fallen and the box has been rotated.

Example Walkthrough

Input:

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

• First row: ['#', '.', '#'] → Stones fall right, so becomes ['.', '.', '#']
• Second row: ['#', '*', '.'] → Stone can't pass obstacle, so stays ['#', '*', '.']
• Third row: ['#', '.', '.'] → Stone falls rightmost, so becomes ['.', '.', '#']

• New grid size: 3 x 3
• Result:

          [
            ['.', '#', '.'],
            ['.', '*', '.'],
            ['#', '.', '#']
          ]
          

• Stones have all fallen as far right as possible before rotation.
• After rotation, the positions reflect the new orientation.

Time and Space Complexity

Brute-force Approach:

• If we tried to move each stone one step at a time, the worst-case time complexity could be O(m * n * n), where m is the number of rows and n is the number of columns.

• Simulating gravity for each row is O(n) per row, so O(m * n) total.
• Rotating the grid is also O(m * n) as each cell is visited once.
• Overall Time Complexity: O(m * n)
• Space Complexity: O(m * n) for the output grid (rotation), and possibly for modifying the box in-place.

Summary

The "Rotating the Box" problem is elegantly solved by first simulating gravity for stones to fall right, then rotating the grid. The process is broken down into clear steps: gravity simulation per row, then a standard 90-degree rotation. This approach is both efficient and easy to implement, requiring only simple matrix manipulations and careful iteration. By separating concerns (gravity then rotation), the solution remains readable and maintainable.

Code Implementation

class Solution:
    def rotateTheBox(self, box):
        m, n = len(box), len(box[0])
        # Simulate gravity: stones fall right
        for row in box:
            write = n - 1
            for col in range(n - 1, -1, -1):
                if row[col] == '*':
                    write = col - 1
                elif row[col] == '#':
                    row[col] = '.'
                    row[write] = '#'
                    write -= 1
        # Rotate 90 degrees clockwise
        rotated = [[None] * m for _ in range(n)]
        for i in range(m):
            for j in range(n):
                rotated[j][m - 1 - i] = box[i][j]
        return rotated
      

class Solution {
public:
    vector<vector<char>> rotateTheBox(vector<vector<char>>& box) {
        int m = box.size(), n = box[0].size();
        // Simulate gravity: stones fall right
        for (int i = 0; i < m; ++i) {
            int write = n - 1;
            for (int j = n - 1; j >= 0; --j) {
                if (box[i][j] == '*') {
                    write = j - 1;
                } else if (box[i][j] == '#') {
                    box[i][j] = '.';
                    box[i][write] = '#';
                    --write;
                }
            }
        }
        // Rotate 90 degrees clockwise
        vector<vector<char>> rotated(n, vector<char>(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;
    }
};
      

class Solution {
    public char[][] rotateTheBox(char[][] box) {
        int m = box.length, n = box[0].length;
        // Simulate gravity: stones fall right
        for (int i = 0; i < m; ++i) {
            int write = n - 1;
            for (int j = n - 1; j >= 0; --j) {
                if (box[i][j] == '*') {
                    write = j - 1;
                } else if (box[i][j] == '#') {
                    box[i][j] = '.';
                    box[i][write] = '#';
                    --write;
                }
            }
        }
        // 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;
    }
}
      

var rotateTheBox = function(box) {
    let m = box.length, n = box[0].length;
    // Simulate gravity: stones fall right
    for (let i = 0; i < m; ++i) {
        let write = n - 1;
        for (let j = n - 1; j >= 0; --j) {
            if (box[i][j] === '*') {
                write = j - 1;
            } else if (box[i][j] === '#') {
                box[i][j] = '.';
                box[i][write] = '#';
                --write;
            }
        }
    }
    // Rotate 90 degrees clockwise
    let rotated = Array.from({length: n}, () => Array(m));
    for (let i = 0; i < m; ++i) {
        for (let j = 0; j < n; ++j) {
            rotated[j][m - 1 - i] = box[i][j];
        }
    }
    return rotated;
};