Similar Problems
Similar Problems not available
Rotating The Box - Leetcode Solution
Companies:
LeetCode: Rotating The Box Leetcode Solution
Difficulty: Medium
Topics: matrix array two-pointers
Problem statement: You are given an m x n matrix of characters box representing a side-view of a box. Each cell of the box is one of the following:
- A stone '#' character
- A stationary obstacle '*' character
- Empty '.' character
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 of the stones does not allow a stone to move left or right.
Example:
Input: box = [["#",".","#"]] Output: [["."], ["#"], ["#"]]
Solution:
- Iterate through each row of the input box.
- For each row, iterate through each column from right to left.
- If a stone '#' character is found, check if there is space below it in the current column.
- If there is empty '.', move the stone down to the empty space and set the original location to empty.
- If there is an obstacle '*' or another stone '#', check if there is empty space to the left of the obstacle/stone.
- If there is empty space to the left, move the stone to the empty space and set the original location to empty.
- If there is no empty space to the left, the stone remains in its original position.
- After iterating through all rows and columns, return the rotated box.
Sample code:
class Solution: def rotateTheBox(self, box: List[List[str]]) -> List[List[str]]:
# Helper function to move stone to new location and set original location to empty
def move_stone(box: List[List[str]], row: int, col: int, new_row: int, new_col: int) -> None:
box[new_row][new_col] = '#'
box[row][col] = '.'
m, n = len(box), len(box[0])
# Iterate through each row
for i in range(m):
row = box[i]
j = n - 1
k = n - 1
# Iterate through each column from right to left
while j >= 0:
# If stone is found in current column, check if there is space below it
if row[j] == '#':
if j < k:
k = j
if j == 0 or row[j-1] != '#':
empty_row = i
# Move stone down to empty space
while empty_row < m and box[empty_row][j] == '.':
move_stone(box, empty_row, j, empty_row-1, j)
empty_row += 1
# Check if there is obstacle or stone to the left
if j > 0 and (box[empty_row-1][j-1] == '#' or box[empty_row-1][j-1] == '*'):
k = j - 1
# Move stone to empty space to the left
if k < j:
empty_row = i
while empty_row < m and box[empty_row][k] == '.':
move_stone(box, empty_row, j, empty_row, k)
empty_row += 1
k -= 1
j -= 1
# Rotate box 90 degrees clockwise
rotated_box = [[0] * m for _ in range(n)]
for i in range(n):
for j in range(m):
rotated_box[i][j] = box[m-j-1][i]
return rotated_box
Time Complexity: The code iterates through each element in the input box once, so the time complexity is O(m*n), where m and n are the dimensions of the input box.
Space Complexity: The code creates a new rotated_box with dimensions nm, so the space complexity is O(mn).
Rotating The Box Solution Code
1