1861. Rotating the Box
Problem Description
In this problem, we are provided with a 2D matrix box
, which represents the side view of a box containing stones ('#'
), stationary obstacles ('*'
), and empty spaces ('.'
). Our goal is to simulate what happens to the stones when the box is rotated 90 degrees clockwise. Importantly, gravity comes into play and the stones may fall down towards the new bottom of the box until they either hit the bottom, an obstacle, or another stone. Unlike the stones, obstacles do not move due to gravity. The problem guarantees that before the rotation, each stone is stable, meaning it's either on the bottom, on an obstacle, or on another stone.
The task is to return a new matrix that represents the final state of the box after rotation and gravity have affected the position of the stones.
Intuition
The solution approach can be divided into two key parts - rotation and gravity handling:
-
Rotate the box by 90 degrees clockwise: This step requires transforming the coordinates of each cell in the original box. The original cell at
(i, j)
will move to(j, m - i - 1)
in the rotated matrix, wherem
is the number of rows in the original matrix. -
Apply gravity to stones: This step simulates the effect of gravity on the stones. After rotation, we need to process each new column (which corresponds to a row in the original box from bottom to top) and let each stone fall down. This is done by keeping track of empty spaces where a stone could fall. We can use a queue to remember the position of the empty spaces. When we encounter a stone, we try to let it fall to the lowest available empty space tracked by our queue. If we encounter an obstacle, we reset the queue as stones cannot pass through obstacles.
By sequentially applying these two steps to the initial box, we achieve the desired final state.
Learn more about Two Pointers patterns.
Solution Approach
The solution is implemented in a few clear steps:
-
Rotation: To perform the 90-degree clockwise rotation of the
m x n
matrix, we need to create a newn x m
matrix. For each cell in the original matrix, which is at position(i, j)
, we place it in the new matrix at position(j, m - i - 1)
. This effectively rotates the matrix while preserving the relative positions of stones, obstacles, and empty spaces. -
Gravity simulation: After the rotation, we need to simulate gravity. This is where an understanding of the new orientation is crucial. What were originally the rows of the original box now become columns, and gravity will act 'downwards' along these new columns.
To handle the gravity, we start at the bottom-most cell of each new column (which corresponds to the right-most cells of the original rows before rotation) and move upward:
a. If we find a stone (
'#'
), we check if we have previously encountered any empty space (which would bedeque
in the example). If we have, we place the stone in the lowest encountered empty space position, which we can get by popping from the left side of thedeque
. Then we mark the original stone position as empty.b. If we find an obstacle (
'*'
), we clear ourdeque
because stones cannot pass through obstacles, so any encountered empty spaces above the obstacle can no longer be filled by stones from below.c. If we find an empty space (
'.'
), we add its position to ourdeque
, as it's a potential space where a stone could fall if a stone is encountered later.
By sequentially rotating the box and then applying gravity, we correctly simulate the effect of the box's rotation on the stones. The use of a deque
is integral to tracking the potential 'fall points' for the stones and ensures that we process them in the right order (the 'lowest' empty space the stone can fall to). Once all columns have been processed, the ans
matrix fully represents the state of the box after rotation and gravity have been applied.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's illustrate the solution approach using a small example:
Suppose we have the following box
matrix:
[ ['#', '.', '#'], ['#', '*', '.'], ['#', '#', '.'] ]
This box is a 3x3
matrix where the first column contains stones stacked on top of each other, the second column has a stone on top, an obstacle in the middle, and an empty space at the bottom, and the third column has two stones on top with an empty space at the bottom.
Step 1: Rotation
If we rotate the box 90 degrees clockwise, the positions change as follows:
- The top row of the original matrix (
['#', '.', '#']
) becomes the first column of the rotated matrix. - The middle row of the original matrix (
['#', '*', '.']
) becomes the second column of the rotated matrix. - The bottom row of the original matrix (
['#', '#', '.']
) becomes the third column of the rotated matrix.
So after rotation, our matrix ans
looks like this:
[ ['#', '#', '#'], ['.', '*', '#'], ['#', '.', '.'] ]
Step 2: Gravity simulation
Now we simulate gravity on the rotated matrix:
- For the first column, no stones are above empty spaces, so no changes occur after simulating gravity.
- For the second column, the stone at position
[1, 1]
('*'
) is an obstacle, and it doesn't fall. There are no stones above it, so this column remains unchanged as well. - For the third column, we have one stone at
[1, 2]
which is above two empty spaces. It will fall to the bottom-most empty space at[2, 2]
. After this stone falls, the column looks like['.', '.', '#']
.
Finally, after applying gravity to each column, the matrix ans
is:
[ ['#', '#', '#'], ['.', '*', '.'], ['#', '.', '#'] ]
This matrix represents the final state of the box after rotation and the effect of gravity on the stones. The stone from the third column of the rotated matrix has fallen down, and we now have a stone at the bottom of the last column.
Solution Implementation
1from collections import deque
2
3class Solution:
4 def rotate_the_box(self, box: List[List[str]]) -> List[List[str]]:
5 # First, get the dimensions of the box
6 rows, cols = len(box), len(box[0])
7
8 # Initialize the answer matrix with None, rotated 90 degrees
9 rotated_box = [[None] * rows for _ in range(cols)]
10
11 # Rotate the box 90 degrees clockwise to the right
12 for row in range(rows):
13 for col in range(cols):
14 rotated_box[col][rows - row - 1] = box[row][col]
15
16 # For each column of the rotated box (which were rows in the original box)
17 for col in range(rows):
18 queue = deque() # Initialize a queue to store the positions of empty '.' slots
19 # Start from bottom and go upwards
20 for row in reversed(range(cols)):
21 # When we see an obstacle '*', we clear the queue as it can't be passed
22 if rotated_box[row][col] == '*':
23 queue.clear()
24 # If it's empty '.', add this position to the queue
25 elif rotated_box[row][col] == '.':
26 queue.append(row)
27 # When we find a stone '#', and there is an available position below it (recorded in the queue)
28 elif queue:
29 new_pos = queue.popleft() # Take the lowest available position
30 rotated_box[new_pos][col] = '#' # Move the stone to the new position
31 rotated_box[row][col] = '.' # Update the old position to empty '.'
32 queue.append(row) # The old position is now a new empty position
33 return rotated_box
34
1class Solution {
2
3 // Method to rotate the box and let the stones fall down due to gravity
4 public char[][] rotateTheBox(char[][] box) {
5 int rows = box.length; // Number of rows in the box
6 int cols = box[0].length; // Number of columns in the box
7 char[][] rotatedBox = new char[cols][rows]; // Resultant array after rotation
8
9 // Rotate the box by 90 degrees clockwise. The bottom becomes the right side.
10 for (int row = 0; row < rows; ++row) {
11 for (int col = 0; col < cols; ++col) {
12 rotatedBox[col][rows - row - 1] = box[row][col];
13 }
14 }
15
16 // Simulate gravity after rotation. Stones fall down to the bottom (right side of the original box).
17 for (int col = 0; col < rows; ++col) {
18 Deque<Integer> emptySpaces = new ArrayDeque<>(); // Queue to track empty spaces (.)
19 for (int row = cols - 1; row >= 0; --row) {
20 // If there's an obstacle, clear the queue as we can't move stones across obstacles.
21 if (rotatedBox[row][col] == '*') {
22 emptySpaces.clear();
23 }
24 // If the cell is empty, keep track of the row index.
25 else if (rotatedBox[row][col] == '.') {
26 emptySpaces.offer(row);
27 }
28 // If there's a stone, move it down if there's an empty space under it.
29 else if (!emptySpaces.isEmpty()) {
30 rotatedBox[emptySpaces.pollFirst()][col] = '#'; // Move stone to the next empty space.
31 rotatedBox[row][col] = '.'; // Make the original place of the stone empty.
32 emptySpaces.offer(row); // Now the old place of the stone is an empty space.
33 }
34 }
35 }
36 return rotatedBox; // Return the box after rotation and gravity simulation
37 }
38}
39
1class Solution {
2public:
3 vector<vector<char>> rotateTheBox(vector<vector<char>>& box) {
4 // Get dimensions of the box
5 int rows = box.size(), cols = box[0].size();
6
7 // Initialize the answer matrix with dimensions swapped (rotated)
8 vector<vector<char>> rotatedBox(cols, vector<char>(rows));
9
10 // Rotate the box clockwise by 90 degrees
11 for (int row = 0; row < rows; ++row) {
12 for (int col = 0; col < cols; ++col) {
13 // Assign values from the original box to the rotated box
14 rotatedBox[col][rows - row - 1] = box[row][col];
15 }
16 }
17
18 // Handle gravity - make stones fall down after rotation
19 for (int col = 0; col < rows; ++col) {
20 queue<int> emptySpaces; // Queue to keep track of empty spaces where stones can fall
21
22 for (int row = cols - 1; row >= 0; --row) {
23 if (rotatedBox[row][col] == '*') {
24 // Encountered an obstacle; clear the queue of empty spaces
25 queue<int> tempQueue;
26 swap(tempQueue, emptySpaces);
27 } else if (rotatedBox[row][col] == '.') {
28 // Found an empty space; add its position to the queue
29 emptySpaces.push(row);
30 } else if (!emptySpaces.empty()) {
31 // We found a stone and there's an empty space below it
32 // Move the stone down to the nearest empty space
33 rotatedBox[emptySpaces.front()][col] = '#';
34 // Mark the old position as empty
35 rotatedBox[row][col] = '.';
36 // Update the queue for the next available empty space
37 emptySpaces.push(row);
38 // Remove the space just filled from the queue
39 emptySpaces.pop();
40 }
41 }
42 }
43
44 // Return the rotated box with stones fallen due to gravity
45 return rotatedBox;
46 }
47};
48
1type Box = char[][]; // Define type alias for readability
2
3// Rotate the box by 90 degrees and let the stones fall with gravity
4function rotateTheBox(box: Box): Box {
5 // Get the dimensions of the box
6 const rows: number = box.length;
7 const cols: number = box[0].length;
8
9 // Initialize the answer matrix with swapped dimensions (rotated box)
10 let rotatedBox: Box = new Array(cols).fill(null).map(() => new Array(rows).fill('.'));
11
12 // Rotate the box clockwise by 90 degrees
13 for (let row = 0; row < rows; ++row) {
14 for (let col = 0; col < cols; ++col) {
15 // Assign values from the original box to the rotated box
16 rotatedBox[col][rows - row - 1] = box[row][col];
17 }
18 }
19
20 // Process gravity in the rotated box
21 for (let col = 0; col < rows; ++col) {
22 let emptySpaces: number[] = []; // Track empty spaces where stones can fall
23
24 for (let row = cols - 1; row >= 0; --row) {
25 if (rotatedBox[row][col] === '*') {
26 // Encountered an obstacle, reset the list of empty spaces
27 emptySpaces = [];
28 } else if (rotatedBox[row][col] === '.') {
29 // Found an empty space, add its position to the list
30 emptySpaces.push(row);
31 } else if (emptySpaces.length > 0) {
32 // Found a stone and there's an empty space below it
33 // Move the stone down to the nearest empty space
34 rotatedBox[emptySpaces[0]][col] = '#';
35 // Mark the old position as empty
36 rotatedBox[row][col] = '.';
37 // Add the position of the moved stone to the list of empty spaces and remove the one just filled
38 emptySpaces.shift();
39 emptySpaces.push(row);
40 }
41 }
42 }
43
44 // Return the rotated box with stones affected by gravity
45 return rotatedBox;
46}
47
Time and Space Complexity
Time Complexity
The time complexity of the given code can be analyzed in two main parts: rotation and gravity simulation.
-
Rotation: The nested loops used for rotating the box iterate
m
times for each of then
columns, which results in a time complexity ofO(m * n)
for this part. -
Gravity simulation: The inner loop for gravity simulation also iterates
n
times for each of them
columns. However, while thedeque
operations (popleft
andappend
) areO(1)
in average cases, clearing thedeque
can also be considered to have an amortized time complexity ofO(1)
since each stone (#
) or obstacle (*
) needs to be moved or evaluated only once across the entire process.
Hence, the time complexity of the gravity simulation is also O(m * n)
.
Combining both parts, the overall time complexity of the algorithm remains O(m * n)
since these parts are sequential and not nested on top of each other.
Space Complexity
The space complexity can be primarily attributed to the space needed for the rotated ans
array and the deque
used for gravity simulation.
-
The
ans
array is of sizem * n
, which is the same as the input box size, hence giving us a space complexity ofO(m * n)
for theans
array. -
The space used by the
deque
could at most holdn
positions in the worst case, which would occur if there was a column filled with empty spaces followed by a stone at the bottom. Therefore, the space complexity for thedeque
isO(n)
.
Since O(m * n)
is the dominating term, the overall space complexity of the given code is O(m * n)
.
In summary:
- Time Complexity:
O(m * n)
- Space Complexity:
O(m * n)
Learn more about how to find time and space complexity quickly using problem constraints.
In a binary min heap, the minimum element can be found in:
Recommended Readings
Tech Interview Pattern Two Pointers Introduction If you prefer videos here's a super quick introduction to Two Pointers div class responsive iframe iframe src https www youtube com embed xZ4AfXHQ1VQ title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture allowfullscreen iframe div Two pointers is a common interview
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Want a Structured Path to Master System Design Too? Donāt Miss This!