Rotating the Box Solution In C++/Python/java/JS
Rotating the Box 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.
Explanation
We have a given m x n grid representing the side view of a box, containing stones ('#'), immovable obstacles ('*'), and empty spaces ('.').
Our task is to rotate the box 90 degrees clockwise and then apply gravity, ensuring that the stones fall as far down as possible while obstacles remain fixed. After these transformations, we need to return the final n x m grid representing the updated box layout.
Example
Input: boxGrid = [["#",".","#"]]
Output: [["."],
["#"],
["#"]]
Explanation:
After rotating the grid 90° clockwise, the row ["#", ".", "#"] becomes a column. Initially, stones (#) may be in the air. Due to gravity, they fall to the lowest available position. The final result has an empty cell (.) at the top and both stones stacked at the bottom.
Input: boxGrid = [["#",".","*","."],
["#","#","*","."]]
Output: [["#","."],
["#","#"],
["*","*"],
[".","."]]
Explanation:
After rotating 90° clockwise, each row becomes a column. The stones (#) then fall to the lowest available positions while obstacles (*) remain fixed, resulting in the final grid.
Input: boxGrid = [["#","#","*",".","*","."],
["#","#","#","*",".","."],
["#","#","#",".","#","."]]
Output: [[".","#","#"],
[".","#","#"],
["#","#","*"],
["#","*","."],
["#",".","*"],
["#",".","."]]
Explanation:
The grid is rotated 90° clockwise, turning rows into columns. Gravity causes the stones (#) to drop down until they land on obstacles (*) or the bottom, forming the final structure.
Constraints
- m == boxGrid.length
- n == boxGrid[i].length
- 1 <= m, n <= 500
- boxGrid[i][j] is either '#', '*', or '.'.
"Rotating the Box" Problem can be solved using different approaches, such as Brute Force and Optimized Iteration. Each approach has its advantages and trade-offs in terms of speed and memory usage.
Brute Force Approach
Intuition
The most straightforward way to solve this problem is to first rotate the box and then simulate gravity row by row to let the stones (#) fall.
Let's first see how rotation works, with some examples:
Example 1: original matrix (1x2) = ['A', 'B']
After rotating 90 degrees clockwise, it becomes:
[['A'],
['B']]
The 1×2 grid became a 2×1 grid after rotation.
Example 2: original matrix (2x3) = [['A', 'B', 'C'], ['D', 'E', 'F']]
After rotating 90 degrees clockwise, it becomes:
[['D', 'A'],
['E', 'B'],
['F', 'C']]
The 2×3 grid became a 3x2 grid after rotation.
So, when we rotate a grid, its shape changes from m×n to n×m.
In mathematics, we call this process the Transpose of a Matrix.
What is the Transpose of a Matrix?
The transpose of a matrix is formed by flipping its rows and columns. In other words, the element at row i and column j in the original matrix moves to row j and column i in the transposed matrix.
How Do We Transpose a Matrix?
- Create a new matrix where the number of rows in the original becomes the columns, and the number of columns becomes the rows.
- Copy each element from the original matrix to its new position in the transposed matrix.
Example:
Consider this 2×3 matrix (2 rows, 3 columns):
[ [1, 2, 3],
[4, 5, 6] ]
When we take its transpose, the rows become columns, resulting in a 3×2 matrix (3 rows, 2 columns):
[ [1, 4],
[2, 5],
[3, 6] ]
This is the transposed matrix. Now, we need to process it further to achieve a 90-degree rotation.
If we compare the transposed matrix and the 90-degree rotated matrix:
original matrix: [[1, 2, 3], [4, 5, 6]]
transposed matrix: [[1, 4], [2, 5], [3, 6]]
90-degree rotated matrix: [[4, 1], [5, 2], [6, 3]]
The values in each row are in reverse order, so we need to reverse each row in the transposed matrix to get the rotated matrix.
How Do We Rotate the Box?
Now that we have the transposed matrix, we need to complete the 90-degree clockwise rotation. To do this, we simply reverse the order of elements in each row.
Steps to Rotate the Matrix
- Take the transposed matrix.
- Reverse the elements in each row to complete the 90-degree clockwise rotation.
Example:
Consider this 2×3 matrix (2 rows, 3 columns):
[ [1, 2, 3],
[4, 5, 6] ]
The transposed matrix:
[ [1, 4],
[2, 5],
[3, 6] ]
Now, we reverse each row:
[ [4, 1],
[5, 2],
[6, 3] ]
This is the final matrix after a 90-degree clockwise rotation.
By following these two steps—transposing the matrix and then reversing each row—we successfully rotate the box as required.
How Do the Stones Fall After Rotation?
After rotating the box, we need to simulate the effect of gravity on the stones (#). The stones should fall as far down as possible while respecting the positions of obstacles (*) and other stones.
We process the rotated grid column by column, starting from the bottom row and moving upward. This ensures that each stone is moved only after checking all possible positions below it.
Let's Understand with an Example
boxGrid = [ ['#', '#', '.'],
['#', '.', '*'],
['#', '*', '.'] ]
Rotating the box by 90°:
Apply Gravity (Process Columns from Bottom to Top):
Column 1:
Column 2:
Column 3:
By following this approach—processing each column from bottom to top—we ensure that every stone lands in the lowest possible position while obeying the constraints.
Rotating the Box Algorithm
- We determine m (rows) and n (columns) of the box grid.
- We create an empty n x m grid result to store the rotated box.
- We transpose the box by placing each element at result[j][i] = box[i][j], swapping rows with columns.
- We reverse each row in result to complete the 90° clockwise rotation.
- We iterate over each column from 0 to m-1, processing elements from bottom to top.
- If we find an empty cell (.), we search above for a stone (#) and move it down to the lowest available empty cell, ensuring it doesn't pass through obstacles (*).
- We return result, which now represents the rotated box with stones properly settled.
Approach
Initialize the Result Grid: Create an n x m grid called result to store the rotated version of the given m x n box.
Transpose the Box:
- Swap rows with columns by iterating through each element of box and placing it in its transposed position in result.
- This step converts the original grid into its transposed form.
Reverse Each Row: Since rotating a matrix 90° clockwise is equivalent to transposing it and then reversing each row, reverse every row in result.
Apply Gravity:
- Iterate through each column from bottom to top.
- If an empty cell (.) is found, search for a stone (#) in the rows above.
- If a stone is found, move it to the lowest available empty cell while keeping obstacles (*) fixed.
Return the Final Grid: After applying gravity, return the updated result grid.
Dry-Run
General Setup:
Input: boxGrid =
[['#', '.', '*'],
['#', '#', '.'],
['#', '*', '.']]
Output:
[['#', '.', '.'],
['*', '.', '#'],
['.', '#', '*']]
Explanation
Step 1: Transpose the Matrix
We swap rows and columns to get the transposed matrix:
[['#', '#', '#'],
['.', '#', '*'],
['*', '.', '.']]
Step 2: Reverse Each Row
Reversing every row gives the 90° rotated matrix:
[['#', '#', '#'],
['*', '#', '.'],
['.', '.', '*']]
Step 3: Apply Gravity (Move Stones Down)
We process each column from bottom to top:
Column 0 (['#', '*', '.']):
→ # remains in place since there's no empty cell below.
→ * remains fixed.
→ '.' stays empty.
Column 1 (['#', '#', '.']):
→ The first # at (0,1) stays.
→ The second # at (1,1) falls into the empty cell at (2,1), swapping positions.
Updated Column 1: ['#', '.', '#']
Column 2 (['#', '.', '*']):
→ # falls into the lowest available empty cell.
→ * remains fixed.
Updated Column 2: ['.', '#', '*']
Final Rotated & Settled Grid:
[['#', '.', '.'],
['*', '.', '#'],
['.', '#', '*']]
This is the final output after rotating the box and letting stones fall.
Rotating the Box solution
Let now discover the codes for Rotating the Box problem in C++, Java, Python, and JavaScript
Brute Force Code in all Languages.
1. Rotating the Box solution in C++ Try on Compiler
class Solution {
public:
// Function to rotate the box 90 degrees clockwise
vector<vector<char>> rotateTheBox(vector<vector<char>>& box) {
// Get the dimensions of the input box
int m = box.size();
int n = box[0].size();
// Initialize the result matrix with transposed dimensions
vector<vector<char>> result(n, vector<char>(m));
// Create the transpose of the input grid in `result`
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
result[i][j] = box[j][i];
}
}
// Reverse each row in the transpose grid to complete the 90° rotation
for (int i = 0; i < n; i++) {
reverseRow(result[i]);
}
// Apply gravity so that stones fall to the lowest possible position
for (int j = 0; j < m; j++) {
for (int i = n - 1; i >= 0; i--) {
if (result[i][j] == '.') {
int nextRowWithStone = -1;
// Look for a stone directly above the empty cell
for (int k = i - 1; k >= 0; k--) {
if (result[k][j] == '*') break; // Obstacle found
if (result[k][j] == '#') { // Stone found
nextRowWithStone = k;
break;
}
}
// If a stone was found, move it down to the empty cell
if (nextRowWithStone != -1) {
result[nextRowWithStone][j] = '.';
result[i][j] = '#';
}
}
}
}
return result;
}
private:
// Helper function to reverse an array
void reverseRow(vector<char>& row) {
int left = 0;
int right = row.size() - 1;
while (left < right) {
char temp = row[left];
row[left] = row[right];
row[right] = temp;
left++;
right--;
}
}
};
2. Rotating the Box solution in Java Try on Compiler
class Solution {
public static char[][] rotateTheBox(char[][] box) {
// Get the number of rows (m) and columns (n) in the original grid
int m = box.length;
int n = box[0].length;
// Create an empty result grid of size n x m to store the rotated box
char[][] result = new char[n][m];
// Create the transpose of the input grid in `result`
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
result[i][j] = box[j][i];
}
}
// Reverse each row in the transpose grid to complete the 90-degree rotation
for (int i = 0; i < n; i++) {
reverse(result[i]);
}
// Apply gravity to let stones fall to the lowest possible empty cell in each column
for (int j = 0; j < m; j++) {
// Process each cell in column `j` from bottom to top
for (int i = n - 1; i >= 0; i--) {
// Found an empty cell; check if a stone can fall into it
if (result[i][j] == '.') {
int nextRowWithStone = -1;
// Look for a stone directly above the empty cell `result[i][j]`
for (int k = i - 1; k >= 0; k--) {
// Obstacle blocks any stones above
if (result[k][j] == '*') break;
// Stone found with no obstacles in between
if (result[k][j] == '#') {
nextRowWithStone = k;
break;
}
}
// If a stone was found above, let it fall into the empty cell `result[i][j]`
if (nextRowWithStone != -1) {
result[nextRowWithStone][j] = '.';
result[i][j] = '#';
}
}
}
}
// Return the final rotated and gravity-applied result grid
return result;
}
// Helper function to reverse an array
private static void reverse(char[] row) {
int left = 0;
int right = row.length - 1;
while (left < right) {
char temp = row[left];
row[left] = row[right];
row[right] = temp;
left++;
right--;
}
}
}3. Rotating the Box solution in Python Try on Compiler
class Solution:
# Function to rotate the box 90 degrees clockwise
def rotateTheBox(self, box: List[List[str]]) -> List[List[str]]:
# Get the dimensions of the input box
m = len(box)
n = len(box[0])
# Initialize the result matrix with transposed dimensions
result = [["" for _ in range(m)] for _ in range(n)]
# Create the transpose of the input grid in `result`
for i in range(n):
for j in range(m):
result[i][j] = box[j][i]
# Reverse each row in the transpose grid to complete the 90° rotation
for i in range(n):
result[i].reverse()
# Apply gravity so that stones fall to the lowest possible position
for j in range(m):
for i in range(n - 1, -1, -1):
if result[i][j] == ".":
next_row_with_stone = -1
# Look for a stone directly above the empty cell
for k in range(i - 1, -1, -1):
if result[k][j] == "*":
break # Obstacle found
if result[k][j] == "#": # Stone found
next_row_with_stone = k
break
# If a stone was found, move it down to the empty cell
if next_row_with_stone != -1:
result[next_row_with_stone][j] = "."
result[i][j] = "#"
return result4. Rotating the Box solution in JavaScript Try on Compiler
/**
* @param {character[][]} boxGrid
* @return {character[][]}
*/
var rotateTheBox = function(boxGrid) {
// Get the dimensions of the input box
const m = boxGrid.length;
const n = boxGrid[0].length;
// Initialize the result matrix with transposed dimensions
let result = Array.from({ length: n }, () => Array(m).fill(""));
// Create the transpose of the input grid in `result`
for (let i = 0; i < n; i++) {
for (let j = 0; j < m; j++) {
result[i][j] = boxGrid[j][i];
}
}
// Reverse each row in the transpose grid to complete the 90° rotation
for (let i = 0; i < n; i++) {
reverseRow(result[i]);
}
// Apply gravity so that stones fall to the lowest possible position
for (let j = 0; j < m; j++) {
for (let i = n - 1; i >= 0; i--) {
if (result[i][j] === ".") {
let nextRowWithStone = -1;
// Look for a stone directly above the empty cell
for (let k = i - 1; k >= 0; k--) {
if (result[k][j] === "*") break; // Obstacle found
if (result[k][j] === "#") { // Stone found
nextRowWithStone = k;
break;
}
}
// If a stone was found, move it down to the empty cell
if (nextRowWithStone !== -1) {
result[nextRowWithStone][j] = ".";
result[i][j] = "#";
}
}
}
}
return result;
};
/**
* Helper function to reverse an array
* @param {character[]} row
*/
function reverseRow(row) {
let left = 0;
let right = row.length - 1;
while (left < right) {
[row[left], row[right]] = [row[right], row[left]];
left++;
right--;
}
}Complexity Analysis of the problem
Time Complexity: O(m × n²)
The approach in our solution has the following time complexity analysis:
Transposing the Grid (O(m × n))
- We iterate over each cell in the original m × n grid to place it into the transposed n × m result.
- This requires O(m × n) operations.
Reversing Each Row (O(m × n))
- After transposing, we reverse each of the n rows.
- Reversing a row takes O(m) time, and since there are n rows, the total is O(m × n).
Applying Gravity (O(m × n²))
- We iterate over each column (m columns).
- For each column, we process each row (n rows), resulting in O(m × n) iterations.
- Within this, in the worst case, we scan all rows above a given empty cell, leading to O(n) additional operations.
- Thus, for each column, the worst-case gravity operation is O(n²).
- Over m columns, the total time complexity is O(m × n²).
Final Time Complexity
Adding up all components:
O(m × n) + O(m × n) + O(m × n²) = O(m × n²)
Thus, the overall time complexity of our approach is O(m × n²).
Space Complexity: O(n*m)
Auxiliary Space Complexity refers to the extra space used by the algorithm excluding the input. In our approach, we create a new grid result of size n × m to store the rotated box. Apart from this, we use only a few integer variables to track indices and loop counters. Since this is the only additional data structure used, the auxiliary space complexity is O(n × m).
Total Space Complexity:
The total space complexity considers both the input and any additional storage used. Our input grid is of size n × m, and we create a new grid result of the same size n × m. Thus, the overall space complexity is O(n × m).
Overall space complexity: O(n × m).
Looking at the constraints (1 ≤ m, n ≤ 500), the brute force approach with O(m × n²) complexity runs within acceptable limits, and for larger grids, say n = m = 1000, this approach would become inefficient. The interviewer will be unhappy with this solution. To make the solution scalable and performant in all cases, Let's figure out an optimal approach.
Optimal Approach
Intuition
For our problem, we need to rotate the box 90° clockwise and then let gravity pull stones (#) down to the lowest available positions.
Let's Understand the 90-degree Rotation with an Example
Let's take a simple 3x4 matrix and its rotated version:
Observations:
- The first row (index = 0) in the original matrix (3 x 4) becomes the last column (index = 2) in the rotated matrix (4 x 3).
- The second row (index = 1) becomes the second-last column (index = 1).
- The last row (index = 2) becomes the first column (index = 1).
Thus, for any row i in the original matrix of size m x n, it maps to column m-1-i in the rotated matrix.
Now, let's observe a single row and its corresponding rotated column:
- The first element of a row (column j) moves to row j in the rotated matrix.
- The second element (column j+1) moves to row j+1, and so on.
From these observations, we can derive that an element at position (i, j) in the original matrix moves to (j, m-1-i) in the rotated matrix of size n x m.
Let's understand how gravity works with an Example
Applying gravity on each column:
From above two images, we can observe that:
- Last Stone Falls First: After rotation, the rightmost element in each row moves to the bottom-most position in the new column. If there's no obstacle, it falls to the lowest available empty cell.
- Next Stone Above Falls Next: Once the bottom-most stone is in place, the next stone above it moves downward to occupy the next available empty cell.
- Obstacles Block Falling Stones: If a stone encounters an obstacle (*), it cannot fall past it. The next stone above must settle in the first available empty space above the obstacle.
From the above observations of rotation, we see that the original m x n matrix transforms into an n x m matrix after a 90-degree rotation. Since empty cells (.) remain empty unless replaced by a stone (#) or obstacle (*), we start with an n x m matrix filled with empty cells to ensure a proper transformation.
From the gravity observations, the right-most stone (#) in each row must fall first to the lowest available empty cell in its rotated column. To achieve this, we traverse each row from right to left while maintaining a pointer tracking the lowest empty cell in the rotated matrix, starting from the bottom.
- If a stone (#) is found, we place it at the pointer's position and move the pointer upward.
- If an obstacle (*) is found, we place it in the rotated matrix and reset the pointer to the row above, ensuring stones cannot pass through it.
1st row:
2nd row:
Final output:
By following this approach, we ensure that every stone lands in the lowest possible position while obeying the constraints.
Rotating the Box Algorithm
- We initialize a n x m result matrix filled with '.'.
- We traverse each row of the original matrix from right to left.
- We track the lowest available empty cell for each column in the rotated matrix.
- We place stones (#) in the lowest available empty cell and move the pointer up.
- We place obstacles (*) at their correct positions and reset the pointer above them.
- We return the rotated and gravity-processed matrix.
Approach
Initialize Result Matrix: Create a n x m matrix (result) filled with '.' to store the rotated and gravity-processed version of box.
Process Each Row of the Original Matrix:
- Traverse each row of the original m x n matrix from right to left (to ensure the right-most stone falls first).
- Maintain a pointer lowestRowWithEmptyCell, initialized to the bottom-most row (n-1) of the corresponding column in result.
Apply Gravity While Rotating:
- If a stone (#) is found, place it at lowestRowWithEmptyCell in the rotated matrix and decrement lowestRowWithEmptyCell.
- If an obstacle (*) is found, place it in the rotated matrix at its correct position and reset lowestRowWithEmptyCell to the row directly above the obstacle, ensuring that stones above it cannot fall past it.
Return: The Rotated and Gravity-Adjusted Matrix.
Dry-Run
Example
Input: Matrix (2x4): [['#', '.', '#', '*'], ['#', '#', '.', '.']]
Output: [['.', '.'], ['#', '#'], ['#', '#'], ['.', '*']]
Step 1: Initialize an Empty 4x2 Rotated Matrix
Since the given matrix is 2x4, after rotation, it will be 4x2.
We initialize the result matrix with empty cells (.):
[ ['.', '.'],
['.', '.'],
['.', '.'],
['.', '.']]
Step 2: Process Each Row from Right to Left & Apply Gravity
We iterate over each row from right to left and track the lowest available empty cell in the rotated matrix.
Processing Row 0 (['#', '.', '#', '*'])
- Column Index 3 (Obstacle *)
→ Place * in the rotated matrix at (3, 1).
→ Reset the lowest available row pointer for this column to 2. - Column Index 2 (Stone #)
→ Place # at (2, 1).
→ Move lowest available row pointer to 1. - Column Index 1 (Empty .)
→ Skip it. - Column Index 0 (Stone #)
→ Place # at (1, 1).
→ Move lowest available row pointer to 0.
Rotated Matrix After Processing Row 0:
[['.', '.'],
['.', '#'],
['.', '#'],
['.', '*']]
Processing Row 1 (['#', '#', '.', '.'])
- Column Index 3 (Empty .)
→ Skip it. - Column Index 2 (Empty .)
→ Skip it. - Column Index 1 (Stone #)
→ Place # at (3, 0).
→ Move lowest available row pointer to 2. - Column Index 0 (Stone #)
→ Place # at (2, 0).
→ Move lowest available row pointer to 1.
Final Output:
[['.', '.'],
['#', '#'],
['#', '#'],
['.', '*']]
Rotating the Box solution
Let now discover the codes for Rotating the Box problem in C++, Java, Python, and JavaScript
Optimal Code in all Languages
1. Rotating the Box solution in C++ Try on Compiler
#include <iostream>
#include <vector>
using namespace std;
class Solution {
public:
vector<vector<char>> rotateTheBox(vector<vector<char>>& box) {
// Get the number of rows (m) and columns (n) in the original box
int m = box.size();
int n = box[0].size();
// Initialize the result grid with empty cells ('.')
vector<vector<char>> result(n, vector<char>(m, '.'));
// Process each row to apply gravity and rotate the box
for (int i = 0; i < m; i++) {
// Pointer to track the lowest available empty cell in the rotated column
int lowestRowWithEmptyCell = n - 1;
// Traverse each row from right to left
for (int j = n - 1; j >= 0; j--) {
// If the current cell contains a stone ('#'), let it fall
if (box[i][j] == '#') {
// Place the stone in the lowest available empty cell in the rotated matrix
result[lowestRowWithEmptyCell][m - i - 1] = '#';
// Move the pointer one row upwards
lowestRowWithEmptyCell--;
}
// If the current cell contains an obstacle ('*'), reset the pointer
if (box[i][j] == '*') {
// Place the obstacle at the corresponding position in the rotated matrix
result[j][m - i - 1] = '*';
// Reset the lowest available empty cell pointer to the row above the obstacle
lowestRowWithEmptyCell = j - 1;
}
}
}
// Return the final rotated and gravity-affected matrix
return result;
}
};
int main() {
// Read the number of rows and columns
int m, n;
cin >> m >> n;
// Declare the input matrix
vector<vector<char>> box(m, vector<char>(n));
// Read the input matrix
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
cin >> box[i][j];
}
}
// Create an instance of Solution
Solution sol;
// Get the rotated and gravity-affected matrix
vector<vector<char>> result = sol.rotateTheBox(box);
// Print the output matrix
for (const auto& row : result) {
for (char c : row) {
cout << c << " ";
}
cout << endl;
}
return 0;
}
2. Rotating the Box solution in Java Try on Compiler
import java.util.*;
class Solution {
public char[][] rotateTheBox(char[][] box) {
int m = box.length;
int n = box[0].length;
char[][] result = new char[n][m];
// Initialize the result grid with '.'
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
result[i][j] = '.';
}
}
// Apply gravity to let stones fall to the lowest possible empty cell in each column
for (int i = 0; i < m; i++) {
int lowestRowWithEmptyCell = n - 1;
// Process each cell in row `i` in reversed order
for (int j = n - 1; j >= 0; j--) {
// Found a stone - let it fall to the lowest empty cell
if (box[i][j] == '#') {
// Place it in the correct position in the rotated grid
result[lowestRowWithEmptyCell][m - i - 1] = '#';
lowestRowWithEmptyCell--;
}
// Found an obstacle - reset `lowestRowWithEmptyCell` to the row directly above it
if (box[i][j] == '*') {
// Place the obstacle in the correct position in the rotated grid
result[j][m - i - 1] = '*';
lowestRowWithEmptyCell = j - 1;
}
}
}
return result;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
// Read matrix dimensions
int m = sc.nextInt();
int n = sc.nextInt();
sc.nextLine(); // Consume newline
// Initialize the input matrix
char[][] box = new char[m][n];
for (int i = 0; i < m; i++) {
String line = sc.nextLine();
for (int j = 0; j < n; j++) {
box[i][j] = line.charAt(j);
}
}
// Create solution object and process the matrix
Solution solution = new Solution();
char[][] result = solution.rotateTheBox(box);
// Print the output matrix
for (char[] row : result) {
System.out.println(new String(row));
}
sc.close();
}
}3. Rotating the Box solution in Python Try on Compiler
class Solution:
def rotateTheBox(self, box):
# Get dimensions of the original matrix
m = len(box)
n = len(box[0])
# Initialize the rotated matrix with empty cells ('.')
result = [["." for _ in range(m)] for _ in range(n)]
# Apply gravity to let stones fall to the lowest possible empty cell in each column
for i in range(m):
lowest_row_with_empty_cell = n - 1
# Process each cell in row `i` in reversed order
for j in range(n - 1, -1, -1):
# Found a stone ('#') - let it fall to the lowest empty cell
if box[i][j] == "#":
result[lowest_row_with_empty_cell][m - i - 1] = "#"
lowest_row_with_empty_cell -= 1
# Found an obstacle ('*') - place it and reset `lowest_row_with_empty_cell`
if box[i][j] == "*":
result[j][m - i - 1] = "*"
lowest_row_with_empty_cell = j - 1
return result
# Function to take input and print output
def main():
# Read input dimensions
m, n = map(int, input().split())
# Read the matrix
box = [list(input().strip()) for _ in range(m)]
# Create an instance of Solution
solution = Solution()
# Get the rotated matrix
result = solution.rotateTheBox(box)
# Print the rotated matrix
for row in result:
print("".join(row))
# Run the main function
if __name__ == "__main__":
main()
4. Rotating the Box solution in JavaScript Try on Compiler
const fs = require("fs");
// Read input using fs.readFileSync
const input = fs.readFileSync(0, "utf8").trim().split("\n");
/**
* Rotates the given box matrix 90 degrees clockwise while applying gravity.
* @param {character[][]} boxGrid - The original box grid.
* @return {character[][]} - The rotated box grid.
*/
var rotateTheBox = function (boxGrid) {
// Get dimensions of the original matrix
const m = boxGrid.length;
const n = boxGrid[0].length;
// Initialize the rotated matrix with empty cells ('.')
const result = Array.from({ length: n }, () => Array(m).fill('.'));
// Apply gravity and rotation
for (let i = 0; i < m; i++) {
let lowestRowWithEmptyCell = n - 1;
// Process each row from right to left
for (let j = n - 1; j >= 0; j--) {
// Found a stone ('#'), move it to the lowest available position
if (boxGrid[i][j] === '#') {
result[lowestRowWithEmptyCell][m - i - 1] = '#';
lowestRowWithEmptyCell--;
}
// Found an obstacle ('*'), place it and reset lowest empty position
if (boxGrid[i][j] === '*') {
result[j][m - i - 1] = '*';
lowestRowWithEmptyCell = j - 1;
}
}
}
return result;
};
// Parse input into a 2D character array
const [rows, cols] = input[0].split(" ").map(Number);
const boxGrid = input.slice(1, rows + 1).map(line => line.split(""));
// Get the rotated result
const rotatedBox = rotateTheBox(boxGrid);
// Print the output matrix
console.log(rotatedBox.map(row => row.join("")));
Time Complexity: O(m x n)
The approach efficiently rotates the grid and applies gravity in a structured manner. Below is the detailed breakdown:
Initializing the Result Grid
We create an empty n × m result grid filled with '.'.
- This requires iterating over all n × m cells.
- Time Complexity: O(n × m)
Applying Gravity and Rotating
We traverse each row of the original m × n grid and process its elements from right to left.
- Outer loop (iterating through m rows) → O(m)
- Inner loop (iterating through n columns) → O(n)
- Each cell is processed once, leading to a total time complexity of O(m × n).
Final Complexity Calculation
- Initializing the result grid: O(n × m)
- Processing each element with gravity and rotation: O(m × n)
- Overall Time Complexity: O(m × n) + O(n × m) = O(m × n)
Since each element is visited only once, this is the most optimal approach possible.
Space Complexity: O(m x n)
Auxiliary Space Complexity refers to extra space used beyond the input grid. In this approach, we allocate a new n × m result grid to store the rotated matrix. This requires O(n × m) additional space. No extra data structures (like stacks or queues) are used, making this the only significant auxiliary space.
Total Space Complexity
The total space includes both the input grid and the newly allocated result grid. Input grid takes O(m × n) space and result grid takes O(n × m) space.
Thus, the overall space complexity is O(m × n + n × m) = O(m × n).
Similar Problems
Now, since we have figured out the Find the Minimum Area to Cover All Ones I solution, let's try out similar problems of "Find the Minimum Area to Cover All Ones I".
You are given a 2D binary array grid. You need to find 3 non-overlapping rectangles having non-zero areas with horizontal and vertical sides such that all the 1's in grid lie inside these rectangles.
Return the minimum possible sum of the area of these rectangles.
Note that the rectangles are allowed to touch.