Leetcode 1861: Rotating the Box
You are given an m x n matrix of characters
box, where each cell is a stone (#), a stationary obstacle (*), or an empty space (.). After rotating the box 90 degrees clockwise, gravity will cause stones to fall down until they land on an obstacle, another stone, or the bottom. Return the updated matrix after the stones have fallen.Problem
Approach
Steps
Complexity
Input: The input is an m x n matrix of characters where each cell can either be a stone (`#`), a stationary obstacle (`*`), or an empty space (`.`).
Example: box = [[# , ., *], [#, *, #]]
Constraints:
• 1 <= m, n <= 500
• Each box[i][j] is either '#', '*', or '.'
Output: The output is the updated matrix representing the box after the stones have fallen due to gravity, while obstacles remain stationary.
Example: Output = [[#, .], [#, #], [*, *], [., .]]
Constraints:
• The output is an m x n matrix of characters, representing the new arrangement after the stones have fallen.
Goal: Simulate the rotation and gravity effect to correctly place the stones.
Steps:
• Step 1: Reverse the rows of the matrix to simulate a 90-degree clockwise rotation.
• Step 2: Iterate over each column, from bottom to top, and move the stones downwards, stopping at obstacles or other stones.
• Step 3: Rebuild the matrix by placing stones at the bottom, obstacles where they are, and empty spaces above the stones.
Goal: The constraints are simple, ensuring that the input matrix is not too large and consists only of the allowed characters.
Steps:
• The matrix dimensions are between 1 and 500 for both rows and columns.
• Each character in the matrix is one of '#', '*', or '.'
Assumptions:
• The matrix is guaranteed to contain at least one row and one column.
• The stones are already placed in a valid position, meaning they will rest on an obstacle, another stone, or the bottom of the box.
• Input: Input: [[., ., #]]
• Explanation: After rotating the box 90 degrees and applying gravity, the stone falls to the bottom.
• Input: Input: [[., *, ., #], [., #, *, #]]
• Explanation: The stones fall to the bottom after rotation, and the obstacles remain in place, causing the stones to settle above them.
Approach: The solution involves simulating the 90-degree rotation of the matrix and applying gravity to the stones. We will reverse the rows of the matrix and then process each column to move stones down while respecting obstacles and other stones.
Observations:
• This is a simulation problem where we need to handle gravity and rotation.
• Reversing the matrix rows will simulate the rotation. Then, we need to handle gravity by checking each column from bottom to top.
Steps:
• Step 1: Reverse the matrix to simulate the 90-degree clockwise rotation.
• Step 2: For each column, simulate the effect of gravity by pushing the stones down towards the bottom of the matrix.
• Step 3: Rebuild the matrix with the stones, obstacles, and empty spaces in their new positions.
Empty Inputs:
• The matrix cannot be empty, as it is guaranteed to have at least one stone or obstacle.
Large Inputs:
• The algorithm should be efficient enough to handle matrices with the maximum size of 500x500.
Special Values:
• Consider cases where there are no stones in a column or when all stones are already at the bottom.
Constraints:
• The matrix is guaranteed to have at least one row and one column.
vector<vector<char>> rotateTheBox(vector<vector<char>>& box) {
reverse(box.begin(), box.end());
int m = box.size(), n = box[0].size();
vector<vector<char>> tmp(n, vector<char>(m));
for(int i = 0; i < m; i++)
for(int j = 0; j < n; j++)
tmp[j][i] = box[i][j];
for(int i = 0; i < m; i++) {
int k = n - 1;
for(int j = n - 1; j >= 0; j--) {
if(tmp[j][i] == '#') {
tmp[j][i] = '.'; // o
tmp[k][i] = '#'; // order is important
k--;
} else if(tmp[j][i] == '*') {
k = j - 1;
}else if(tmp[j][i] == '.') {
}
}
}
return tmp;
}
1 : Function Definition
vector<vector<char>> rotateTheBox(vector<vector<char>>& box) {
Define the function `rotateTheBox`, which takes a reference to a 2D vector `box` representing a grid.
2 : Reverse Grid
reverse(box.begin(), box.end());
Reverse the rows of the grid to simulate a vertical flip of the box.
3 : Variable Initialization
int m = box.size(), n = box[0].size();
Store the dimensions of the grid: `m` for the number of rows and `n` for the number of columns.
4 : Matrix Initialization
vector<vector<char>> tmp(n, vector<char>(m));
Create a new grid `tmp` with dimensions transposed from the original grid (`n` rows and `m` columns).
5 : Outer Loop (Rows)
for(int i = 0; i < m; i++)
Start an outer loop to iterate over the rows of the original grid.
6 : Inner Loop (Columns)
for(int j = 0; j < n; j++)
Start an inner loop to iterate over the columns of the original grid.
7 : Transposition
tmp[j][i] = box[i][j];
Transpose the grid, storing the element at `box[i][j]` into the transposed grid `tmp[j][i]`.
8 : Loop through Transposed Grid
for(int i = 0; i < m; i++) {
Start a loop to process each column of the transposed grid.
9 : Initialize k
int k = n - 1;
Initialize `k` to point to the last row in the current column of the transposed grid.
10 : Inner Loop (Process Elements)
for(int j = n - 1; j >= 0; j--) {
Start an inner loop to process each element of the column, from bottom to top.
11 : If Condition (Non-empty Cell)
if(tmp[j][i] == '#') {
Check if the current cell contains a non-empty element (`#`).
12 : Move Cell Down (Empty)
tmp[j][i] = '.'; // o
Set the current cell to empty (`.`) to simulate the removal of the non-empty element.
13 : Move Cell Down (Non-empty)
tmp[k][i] = '#'; // order is important
Place the non-empty element (`#`) into the first available position (at `k`) in the column.
14 : Update k
k--;
Decrease `k` to move to the next available position for the next non-empty element.
15 : Else If Condition (Obstacle)
} else if(tmp[j][i] == '*') {
Check if the current cell contains an obstacle (`*`).
16 : Update k (Obstacle)
k = j - 1;
If the current cell is an obstacle, update `k` to the row before the obstacle.
17 : Else If Condition (Empty Cell)
}else if(tmp[j][i] == '.') {
Check if the current cell is empty (`.`).
18 : Return Result
return tmp;
Return the rotated grid `tmp` after performing all the necessary operations.
Best Case: O(m * n)
Average Case: O(m * n)
Worst Case: O(m * n)
Description: The time complexity is O(m * n), where m is the number of rows and n is the number of columns in the matrix. We process each element once.
Best Case: O(m * n)
Worst Case: O(m * n)
Description: The space complexity is O(m * n) due to the new matrix used to store the updated box state.
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus