Rotating the Box
MedPrompt
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:
Input: boxGrid = [["#",".","#"]]
Output: [["."],
["#"],
["#"]]Example 2:
Input: boxGrid = [["#",".","*","."],
["#","#","*","."]]
Output: [["#","."],
["#","#"],
["*","*"],
[".","."]]Example 3:
Input: boxGrid = [["#","#","*",".","*","."],
["#","#","#","*",".","."],
["#","#","#",".","#","."]]
Output: [[".","#","#"],
[".","#","#"],
["#","#","*"],
["#","*","."],
["#",".","*"],
["#",".","."]]
Constraints:
m == boxGrid.lengthn == boxGrid[i].length1 <= m, n <= 500boxGrid[i][j]is either'#','*', or'.'.
Approaches
3 approaches with complexity analysis and trade-offs.
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.
Algorithm
- Realize that a 90-degree clockwise rotation turns the horizontal 'right' direction into the vertical 'down' direction.
- 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 (*). - Iterate through each row
iofboxGrid. - For each row, use a
write_pospointer, initialized to the last column index (n - 1), to track the rightmost available spot for a stone. - Iterate through the row from right to left (
jfromn - 1down to0). - If
box[i][j]is an obstacle'*', it blocks movement. Resetwrite_postoj - 1. - If
box[i][j]is a stone'#, move it tobox[i][write_pos], setbox[i][j]to'.'(ifj != write_pos), and decrementwrite_pos. - After this in-place modification, the
boxGridnow represents the state after horizontal gravity. - Create the final
n x mresult matrix. - Populate the result matrix by rotating the modified
boxGrid:result[j][m - 1 - i] = box[i][j]. - Return the
resultmatrix.
Walkthrough
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.
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; }}Complexity
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.
Trade-offs
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.
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 (*).
Algorithm
- Get the dimensions of the input
boxGrid,mrows andncolumns. - Create a new
n x mcharacter matrix,rotatedBox, to store the result of the 90-degree clockwise rotation. - Populate
rotatedBoxby mapping each elementboxGrid[i][j]torotatedBox[j][m - 1 - i]. - Now, apply gravity to the
rotatedBox. Iterate through each columncfrom0tom - 1. - For each column, use a pointer
emptyRowinitialized to the last row index (n - 1). This pointer tracks the lowest available position for a stone to fall into. - Iterate upwards through the column, from row
r = n - 1down to0. - If
rotatedBox[r][c]is an obstacle'*', it acts as a new floor. UpdateemptyRowto be the row just above the obstacle, i.e.,r - 1. - If
rotatedBox[r][c]is a stone'#',move it to the current lowest available position. SetrotatedBox[emptyRow][c] = '#'. If the stone was moved (i.e.,r != emptyRow), set its original positionrotatedBox[r][c]to empty'.'. Then, decrementemptyRowto mark the next available spot above the just-placed stone. - After processing all columns,
rotatedBoxwill represent the final state. Return it.
Walkthrough
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.
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; }}Complexity
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.
Trade-offs
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 mmatrix, 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.
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.
Algorithm
- Get the dimensions
mandn. Create the finaln x mresultmatrix and initialize all its cells to'.'. - The key insight is that column
cof the finalresultmatrix corresponds to rowm - 1 - cof the originalboxGrid. - We can build the
resultmatrix column by column. Iterate through the rows of the originalboxGridfromi = 0tom - 1. Each rowiwill determine the contents of columnm - 1 - iin theresultmatrix. - For each row
i, maintain a pointerkinitialized ton - 1. Thiskrepresents the lowest available row index in the target column of theresultmatrix where a stone can be placed. - Iterate through the current row
iofboxGridfrom right to left (fromj = n - 1down to0). - Let
targetCol = m - 1 - i. - 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. - If
boxGrid[i][j]is a stone'#, it falls to the lowest available spotk. Place it atresult[k][targetCol] = '#'and then decrementkto point to the next available spot above it. - Empty cells
'.'inboxGridare ignored, as theresultmatrix is already pre-filled with'.'. - After iterating through all rows of
boxGrid, theresultmatrix is fully constructed with rotation and gravity applied. Returnresult.
Walkthrough
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 atresult[k][m - 1 - i]and move our 'bottom' pointerkup by one (k--). - If
boxGrid[i][j]is an obstacle'*', its position is fixed relative to the rotation. We place it atresult[j][m - 1 - i]. This obstacle now becomes the new 'bottom' for any stones to its left, so we updatektoj - 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.
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; }}Complexity
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.
Trade-offs
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.
Solutions
Solution
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; }}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; }};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 ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.