Problem of The Day: Rotating the Box
Problem Statement
Intuition
The problem requires simulating gravity to drop stones ('#') as far right as possible within the constraints of the obstacles ('*'). Once the stones are settled, the box needs to be rotated 90 degrees clockwise. Breaking the task into two steps—gravity simulation and rotation—makes the solution manageable.
Approach
Step 1: Simulating Gravity
- Traverse each row in the box to count stones (
'#'). - When encountering an obstacle (
'*') or reaching the end of the row, push the stones as far right as possible while leaving spaces ('.') in the original positions. - Maintain a stack to handle any leftover stones at the end of the row.
Step 2: Rotating the Box
- Create a new 2D array to represent the rotated box, where the dimensions are swapped (rows become columns and vice versa).
- Populate the new array by iterating through the original box and transferring elements to their respective positions in the rotated version.
Complexity
-
Time Complexity:
- Simulating gravity takes \(O(R \times C)\) because each element in the box is processed once.
- Rotating the box also takes \(O(R \times C)\) since every element is copied into the new array.
Hence, the total time complexity is \(O(R \times C)\).
-
Space Complexity:
- The rotated box requires \(O(R \times C)\) additional space.
- Other auxiliary storage, such as the stack, is negligible.
Thus, the space complexity is \(O(R \times C)\).
Code
from typing import List
class Solution:
def rotateTheBox(self, box: List[List[str]]) -> List[List[str]]:
ROWS = len(box)
COLS = len(box[0])
STONE = '#'
EMPTY = '.'
BLOCK = '*'
res = []
# Initialize the rotated box with empty spaces
for col in range(COLS):
arr = []
for row in range(ROWS):
arr.append(EMPTY)
res.append(arr)
# Simulate gravity in each row
for r in range(ROWS):
stones = 0
stack = []
for c in range(COLS):
if box[r][c] == STONE:
stones += 1
box[r][c] = EMPTY
if box[r][c] == BLOCK and stones > 0:
stack.append([c, stones])
stones = 0
if stones > 0:
stack.append([COLS, stones])
while stack:
col, left_stones = stack.pop()
for cc in range(col - 1, -1, -1):
box[r][cc] = STONE
left_stones -= 1
if left_stones == 0:
break
# Rotate the box 90 degrees clockwise
for row in range(ROWS):
for col in range(COLS):
value = box[row][col]
res[col][ROWS - row - 1] = value
return res
Revised Code
from typing import List
class Solution:
def rotateTheBox(self, box: List[List[str]]) -> List[List[str]]:
ROWS = len(box)
COLS = len(box[0])
STONE = '#'
EMPTY = '.'
BLOCK = '*'
# Simulate gravity within each row
for r in range(ROWS):
stones = 0
for c in range(COLS):
if box[r][c] == STONE:
stones += 1
box[r][c] = EMPTY
if box[r][c] == BLOCK:
for cc in range(c - 1, c - stones - 1, -1):
box[r][cc] = STONE
stones = 0
# Handle remaining stones after the last obstacle
for cc in range(COLS - 1, COLS - stones - 1, -1):
box[r][cc] = STONE
# Rotate the box 90 degrees clockwise
rotated_box = [[EMPTY for _ in range(ROWS)] for _ in range(COLS)]
for row in range(ROWS):
for col in range(COLS):
rotated_box[col][ROWS - row - 1] = box[row][col]
return rotated_box
Editorial Solution
Approach 1: Row by Row (Brute Force)
class Solution:
def rotateTheBox(self, box: List[List[str]]) -> List[List[str]]:
m = len(box)
n = len(box[0])
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 to let stones fall to the lowest possible empty cell in each column
for j in range(m):
# Process each cell in column `j` from bottom to top
for i in range(n - 1, -1, -1):
if (
result[i][j] == "."
): # Found an empty cell; check if a stone can fall into it
next_row_with_stone = -1
# Look for a stone directly above the empty cell `result[i][j]`
for k in range(i - 1, -1, -1):
if result[k][j] == "*":
break # Obstacle blocks any stones above
if (
result[k][j] == "#"
): # Stone found with no obstacles in between
next_row_with_stone = k
break
# If a stone was found above, let it fall into the empty cell `result[i][j]`
if next_row_with_stone != -1:
result[next_row_with_stone][j] = "."
result[i][j] = "#"
return result
- time: O(m*n^2)
- space: O(m*n)
Approach 2: Row By Row (Optimized)
class Solution:
def rotateTheBox(self, box: List[List[str]]) -> List[List[str]]:
m = len(box)
n = len(box[0])
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 to let stones fall to the lowest possible empty cell in each column
for j in range(m):
lowest_row_with_empty_cell = n - 1
# Process each cell in column `j` from bottom to top
for i in range(n - 1, -1, -1):
# Found a stone - let it fall to the lowest empty cell
if result[i][j] == "#":
result[i][j] = "."
result[lowest_row_with_empty_cell][j] = "#"
lowest_row_with_empty_cell -= 1
# Found an obstacle - reset `lowest_row_with_empty_cell` to the row directly above it
if result[i][j] == "*":
lowest_row_with_empty_cell = i - 1
return result
- time: O(m*n)
- space: O(m*n)
Approach 3: Combine rotation and gravity operations
class Solution:
def rotateTheBox(self, box):
m = len(box)
n = len(box[0])
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] == "#":
# Place it in the correct position in the rotated grid
result[lowest_row_with_empty_cell][m - i - 1] = "#"
lowest_row_with_empty_cell -= 1
# Found an obstacle - reset `lowest_row_with_empty_cell` 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] = "*"
lowest_row_with_empty_cell = j - 1
return result
- time: O(m*n)
- space: O(m*n)
