# Rotating the Box
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/rotating-the-box)
Canonical: https://scaleengineer.com/dsa/problems/rotating-the-box
**Patterns:** [Two Pointers](https://scaleengineer.com/dsa/patterns/two-pointers)
**Data structures:** Array, Matrix
**Companies:** [Roblox](https://scaleengineer.com/companies/roblox), [Visa](https://scaleengineer.com/companies/visa), [Capital One](https://scaleengineer.com/companies/capital-one), [Commvault](https://scaleengineer.com/companies/commvault), [Block](https://scaleengineer.com/companies/block)
---
## Problem
You are given an `m x n` matrix of characters `boxGrid` representing a side-view of a box. Each cell of the box is one of the following:

* A stone `'#'`
* A stationary obstacle `'*'`
* Empty `'.'`

The box is rotated **90 degrees clockwise**, causing some of the stones to fall due to gravity. Each stone falls down until it lands on an obstacle, another stone, or the bottom of the box. Gravity **does not** affect the obstacles' positions, and the inertia from the box's rotation **does not** affect the stones' horizontal positions.

It is **guaranteed** that each stone in `boxGrid` rests on an obstacle, another stone, or the bottom of the box.

Return _an_ `n x m` _matrix representing the box after the rotation described above_.

**Example 1:**

![](https://assets.glich.co/dsa/rotating-the-box/image0.png)

**Input:** boxGrid = [["#",".","#"]]
**Output:** [["."],
         ["#"],
         ["#"]]

**Example 2:**

![](https://assets.glich.co/dsa/rotating-the-box/image1.png)

**Input:** boxGrid = [["#",".","*","."],
              ["#","#","*","."]]
**Output:** [["#","."],
         ["#","#"],
         ["*","*"],
         [".","."]]

**Example 3:**

![](https://assets.glich.co/dsa/rotating-the-box/image2.png)

**Input:** boxGrid = [["#","#","*",".","*","."],
              ["#","#","#","*",".","."],
              ["#","#","#",".","#","."]]
**Output:** [[".","#","#"],
         [".","#","#"],
         ["#","#","*"],
         ["#","*","."],
         ["#",".","*"],
         ["#",".","."]]

**Constraints:**

* `m == boxGrid.length`
* `n == boxGrid[i].length`
* `1 <= m, n <= 500`
* `boxGrid[i][j]` is either `'#'`, `'*'`, or `'.'`.

# Approaches
## Approach 1: Rotate then Apply Gravity
This approach follows the problem description in a literal, step-by-step manner. First, we perform the 90-degree clockwise rotation on the input `boxGrid` to create an intermediate `n x m` matrix. After the rotation is complete, we simulate the effect of gravity on this new matrix. Since gravity pulls stones downwards, we process each column of the rotated matrix independently. For each column, stones (`#`) are moved to the lowest possible empty positions until they hit the bottom, another stone, or an obstacle (`*`).
**Time:** O(m * n). The rotation step takes O(m * n) time to iterate through the original grid. The gravity simulation step also takes O(m * n) time as it iterates through the `n x m` rotated grid. The total time complexity is O(m * n) + O(m * n) = O(m * n). · **Space:** O(m * n), for storing the intermediate `rotatedBox` matrix. This is in addition to the space for the input.
**Pros:** The logic is straightforward and easy to understand as it directly simulates the two distinct physical processes (rotation and falling).; Separating the two concerns (rotation and gravity) can make the code easier to write and debug.
**Cons:** Requires an intermediate `n x m` matrix, leading to higher space consumption compared to other approaches.; Involves two separate full passes over the data (one for rotation, one for gravity), which can be less efficient in practice than a single-pass solution.
### Explanation
The algorithm first allocates a new `n x m` matrix, let's call it `rotatedBox`. It then iterates through the original `m x n` `boxGrid`, placing each element `boxGrid[i][j]` into its new position `rotatedBox[j][m - 1 - i]`. This completes the rotation.

Next, the gravity simulation begins. We iterate through each column of `rotatedBox`. For each column, we use a pointer, say `emptyRow`, to keep track of the bottom-most available row for a stone. This pointer starts at `n-1`. We scan the column from bottom to top. When we encounter a stone, we move it to the `emptyRow` and decrement `emptyRow`. If we encounter an obstacle, it acts as a barrier, and we reset `emptyRow` to be the row right above the obstacle. This process ensures all stones settle at the lowest possible positions within their segments in each column.

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

        // Step 1: Rotate the box 90 degrees clockwise
        char[][] rotatedBox = new char[n][m];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                rotatedBox[j][m - 1 - i] = box[i][j];
            }
        }

        // Step 2: Apply gravity to the rotated box
        for (int j = 0; j < m; j++) { // Iterate through each column
            int emptyRow = n - 1;
            for (int i = n - 1; i >= 0; i--) { // Iterate from bottom to top
                if (rotatedBox[i][j] == '*') {
                    emptyRow = i - 1;
                } else if (rotatedBox[i][j] == '#') {
                    rotatedBox[i][j] = '.';
                    rotatedBox[emptyRow][j] = '#';
                    emptyRow--;
                }
            }
        }

        return rotatedBox;
    }
}
```
### Algorithm
1. Get the dimensions of the input `boxGrid`, `m` rows and `n` columns.
2. Create a new `n x m` character matrix, `rotatedBox`, to store the result of the 90-degree clockwise rotation.
3. Populate `rotatedBox` by mapping each element `boxGrid[i][j]` to `rotatedBox[j][m - 1 - i]`.
4. Now, apply gravity to the `rotatedBox`. Iterate through each column `c` from `0` to `m - 1`.
5. For each column, use a pointer `emptyRow` initialized to the last row index (`n - 1`). This pointer tracks the lowest available position for a stone to fall into.
6. Iterate upwards through the column, from row `r = n - 1` down to `0`.
7. If `rotatedBox[r][c]` is an obstacle `'*'`, it acts as a new floor. Update `emptyRow` to be the row just above the obstacle, i.e., `r - 1`.
8. If `rotatedBox[r][c]` is a stone `'#',` move it to the current lowest available position. Set `rotatedBox[emptyRow][c] = '#'`. If the stone was moved (i.e., `r != emptyRow`), set its original position `rotatedBox[r][c]` to empty `'.'`. Then, decrement `emptyRow` to mark the next available spot above the just-placed stone.
9. After processing all columns, `rotatedBox` will represent the final state. Return it.

## Approach 2: Apply Gravity then Rotate
This approach cleverly reorders the operations. We observe that simulating gravity in the final rotated grid is equivalent to simulating gravity horizontally (to the right) in the original grid. By applying this horizontal gravity first, we can modify the input grid `boxGrid` in-place. After all stones in each row have 'settled' to the right, we then perform the 90-degree clockwise rotation to get the final configuration. This avoids the need for a full intermediate matrix for the initial rotation.
**Time:** O(m * n). The horizontal gravity pass takes O(m * n), and the final rotation pass also takes O(m * n). The total complexity is O(m * n). · **Space:** O(1) auxiliary space. The gravity simulation is done in-place. The O(m * n) space for the final `result` matrix is required by the problem output format and is not considered auxiliary.
**Pros:** More space-efficient as it modifies the input grid in-place for the gravity simulation, avoiding a large intermediate matrix.; The logic remains fairly intuitive by separating the two main steps.
**Cons:** While more space-efficient than the first approach, it still requires two separate passes over the data.; In-place modification of the grid can sometimes be trickier to implement correctly than using an auxiliary data structure.
### Explanation
The core idea is to handle the gravity effect before rotation. For each row in the `m x n` `boxGrid`, we make the stones fall to the 'right'. This can be done efficiently in-place. We iterate through each row from right to left. A `write_pos` pointer keeps track of where the next stone from the left should be placed. When we see a stone, we place it at `write_pos` and move `write_pos` one step to the left. When we see an obstacle, it acts as a wall, and `write_pos` is reset to the position just to the left of the obstacle.

After applying this transformation to all rows of `boxGrid`, we proceed with the rotation. A new `n x m` matrix `result` is created. We then perform the standard 90-degree clockwise rotation, copying elements from the modified `boxGrid` to the `result` matrix. This method is more space-efficient because the gravity simulation is done in-place, eliminating the need for an extra `n x m` matrix used in the first approach.

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

        // Step 1: Apply gravity to each row (stones fall to the right)
        for (int i = 0; i < m; i++) {
            int writePos = n - 1;
            for (int j = n - 1; j >= 0; j--) {
                if (box[i][j] == '*') {
                    writePos = j - 1;
                } else if (box[i][j] == '#') {
                    box[i][j] = '.';
                    box[i][writePos] = '#';
                    writePos--;
                }
            }
        }

        // Step 2: Rotate the modified box
        char[][] result = new char[n][m];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                result[j][m - 1 - i] = box[i][j];
            }
        }

        return result;
    }
}
```
### Algorithm
1. Realize that a 90-degree clockwise rotation turns the horizontal 'right' direction into the vertical 'down' direction.
2. Instead of rotating first, apply gravity horizontally on the original `boxGrid`. This means shifting all stones (`#`) in each row to the rightmost possible positions, respecting obstacles (`*`).
3. Iterate through each row `i` of `boxGrid`.
4. For each row, use a `write_pos` pointer, initialized to the last column index (`n - 1`), to track the rightmost available spot for a stone.
5. Iterate through the row from right to left (`j` from `n - 1` down to `0`).
6. If `box[i][j]` is an obstacle `'*'`, it blocks movement. Reset `write_pos` to `j - 1`.
7. If `box[i][j]` is a stone `'#`, move it to `box[i][write_pos]`, set `box[i][j]` to `'.'` (if `j != write_pos`), and decrement `write_pos`.
8. After this in-place modification, the `boxGrid` now represents the state after horizontal gravity.
9. Create the final `n x m` result matrix.
10. Populate the result matrix by rotating the modified `boxGrid`: `result[j][m - 1 - i] = box[i][j]`.
11. Return the `result` matrix.

## Approach 3: Single-Pass Combined Simulation and Rotation
This is the most optimal approach, which combines the rotation and gravity simulation into a single, efficient pass. We construct the final `n x m` matrix directly, without any intermediate matrices or in-place modifications of the input. The logic hinges on understanding the relationship between the rows of the original box and the columns of the final rotated box. A row `i` in the original `m x n` box becomes column `m - 1 - i` in the final `n x m` box. By iterating through each row of the input and simultaneously placing elements into the correct column of the output, we can apply the gravity logic on-the-fly.
**Time:** O(m * n). The algorithm iterates through each cell of the input `boxGrid` exactly once. · **Space:** O(1) auxiliary space. The space for the `result` matrix is required by the problem statement.
**Pros:** Most efficient in terms of both time and space.; Processes the grid in a single pass, which can lead to better performance due to factors like cache efficiency.; Avoids intermediate data structures and in-place modification of the input.
**Cons:** The mapping between the input grid indices and the output grid indices can be slightly more complex to reason about compared to the two-pass approaches.
### Explanation
We start by creating our `n x m` result matrix, filling it with `.` to represent empty space. Then, we iterate through each row `i` of the input `boxGrid`. For each row `i`, we are essentially building column `m - 1 - i` of our result. We use a pointer `k` (initially `n-1`) to track the current 'bottom' of this target column. We scan row `i` from right to left (from `j=n-1` down to `0`).

- If `boxGrid[i][j]` is a stone `'#`, we know it will fall to the current bottom, so we place it at `result[k][m - 1 - i]` and move our 'bottom' pointer `k` up by one (`k--`).
- If `boxGrid[i][j]` is an obstacle `'*'`, its position is fixed relative to the rotation. We place it at `result[j][m - 1 - i]`. This obstacle now becomes the new 'bottom' for any stones to its left, so we update `k` to `j - 1`.
- If `boxGrid[i][j]` is empty `'.'`, we do nothing, as the result matrix is already filled with `.`.

This single pass over the input grid populates the output grid with the final, correct state, making it the most efficient solution in terms of both time and space.

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

        // Initialize result with empty cells
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                result[i][j] = '.';
            }
        }

        // Process each row of the original box, which corresponds to a column in the result
        for (int i = 0; i < m; i++) {
            int k = n - 1; // Pointer for the lowest available spot in the target column
            int targetCol = m - 1 - i;
            
            // Iterate through the row from right to left
            for (int j = n - 1; j >= 0; j--) {
                if (box[i][j] == '*') {
                    // Obstacle is fixed, place it and update the floor
                    result[j][targetCol] = '*';
                    k = j - 1;
                } else if (box[i][j] == '#') {
                    // Stone falls to the lowest available spot
                    result[k][targetCol] = '#';
                    k--;
                }
            }
        }

        return result;
    }
}
```
### Algorithm
1. Get the dimensions `m` and `n`. Create the final `n x m` `result` matrix and initialize all its cells to `'.'`. 
2. The key insight is that column `c` of the final `result` matrix corresponds to row `m - 1 - c` of the original `boxGrid`.
3. We can build the `result` matrix column by column. Iterate through the rows of the original `boxGrid` from `i = 0` to `m - 1`. Each row `i` will determine the contents of column `m - 1 - i` in the `result` matrix.
4. For each row `i`, maintain a pointer `k` initialized to `n - 1`. This `k` represents the lowest available row index in the target column of the `result` matrix where a stone can be placed.
5. Iterate through the current row `i` of `boxGrid` from right to left (from `j = n - 1` down to `0`).
6. Let `targetCol = m - 1 - i`.
7. If `boxGrid[i][j]` is an obstacle `'*'`, it's fixed in space. Place it directly into the result: `result[j][targetCol] = '*'`. This obstacle also acts as a new floor, so update the lowest available spot for stones: `k = j - 1`.
8. If `boxGrid[i][j]` is a stone `'#`, it falls to the lowest available spot `k`. Place it at `result[k][targetCol] = '#'` and then decrement `k` to point to the next available spot above it.
9. Empty cells `'.'` in `boxGrid` are ignored, as the `result` matrix is already pre-filled with `'.'`. 
10. After iterating through all rows of `boxGrid`, the `result` matrix is fully constructed with rotation and gravity applied. Return `result`.

# Solutions
### Java

```java
class Solution {
public
  char[][] rotateTheBox(char[][] box) {
    int m = box.length, n = box[0].length;
    char[][] ans = new char[n][m];
    for (int i = 0; i < m; ++i) {
      for (int j = 0; j < n; ++j) {
        ans[j][m - i - 1] = box[i][j];
      }
    }
    for (int j = 0; j < m; ++j) {
      Deque<Integer> q = new ArrayDeque<>();
      for (int i = n - 1; i >= 0; --i) {
        if (ans[i][j] == '*') {
          q.clear();
        } else if (ans[i][j] == '.') {
          q.offer(i);
        } else if (!q.isEmpty()) {
          ans[q.pollFirst()][j] = '#';
          ans[i][j] = '.';
          q.offer(i);
        }
      }
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  vector<vector<char>> rotateTheBox(vector<vector<char>> &box) {
    int m = box.size(), n = box[0].size();
    vector<vector<char>> ans(n, vector<char>(m));
    for (int i = 0; i < m; ++i) {
      for (int j = 0; j < n; ++j) {
        ans[j][m - i - 1] = box[i][j];
      }
    }
    for (int j = 0; j < m; ++j) {
      queue<int> q;
      for (int i = n - 1; ~i; --i) {
        if (ans[i][j] == '*') {
          queue<int> t;
          swap(t, q);
        } else if (ans[i][j] == '.') {
          q.push(i);
        } else if (!q.empty()) {
          ans[q.front()][j] = '#';
          q.pop();
          ans[i][j] = '.';
          q.push(i);
        }
      }
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def rotateTheBox(self, box: List[List[str]]) -> List[List[str]]: m, n = len(box), len(box[0]) ans = [[None] * m for _ in range(n)] for i in range(m): for j in range(n): ans[j][m - i - 1] = box[i][j] for j in range(m): q = deque() for i in range(n - 1, - 1, - 1): if ans[i][j] == '*': q . clear() elif ans[i][j] == '.': q . append(i) elif q: ans[q . popleft()][j] = '#' ans[i][j] = '.' q . append(i) return ans

```