LeetCode Solutions Blog

Rotating the Box

Number: 1972

Difficulty: Medium

Paid? No

Problem Description

Given an m x n matrix representing a side-view of a box, where each cell is either a stone ("#"), an obstacle ("*"), or empty ("."). The box is rotated 90 degrees clockwise, and then gravity makes any loose stones fall down until they hit an obstacle, another stone, or the bottom of the box. The obstacles remain in their rotated positions. Return the resulting n x m matrix after the rotation and gravity simulation.

Key Insights

Rotate the box 90 degrees clockwise by remapping indices: element at (i, j) goes to (j, m-1-i).
After the rotation, simulate gravity on each column, making stones fall down.
Use a pointer to track the "available" position (the lowest empty cell) in each column.
The obstacles act as barriers and reset the available pointer for stones above them.

Space and Time Complexity

Time Complexity: O(mn) because each cell is processed a constant number of times. Space Complexity: O(mn) required for the output (rotated) matrix.

Solution

The approach consists of two major steps:

Rotate the matrix 90 degrees clockwise by creating a new matrix where the cell originally at (i, j) maps to (j, m-1-i).
Simulate gravity on the rotated matrix by processing each column from bottom to top. Maintain an "available" pointer that indicates where the next stone ("#") should fall. When an obstacle ("*") is encountered, reset the pointer above the obstacle. Replace stone positions accordingly.

Code Solutions

# Python solution to rotate the box and simulate gravity
def rotateTheBox(box):
    m = len(box)         # number of rows in original box
    n = len(box[0])      # number of columns in original box

    # Initialize rotated grid with empty cells ('.')
    rotated = [['.' for _ in range(m)] for _ in range(n)]
    
    # Step 1: Rotate the box 90 degrees clockwise.
    # Map each element: element at (i, j) moves to (j, m - 1 - i)
    for i in range(m):
        for j in range(n):
            rotated[j][m - 1 - i] = box[i][j]
    
    # Step 2: For each column in rotated grid, simulate gravity for the stones.
    for col in range(m):
        available = n - 1  # pointer for the lowest empty spot in this column
        for row in range(n - 1, -1, -1):
            if rotated[row][col] == '*':  # obstacle encountered
                available = row - 1  # reset available pointer above the obstacle
            elif rotated[row][col] == '#':  # stone encountered
                if available != row:
                    rotated[available][col] = '#'  # drop the stone
                    rotated[row][col] = '.'  # clear the original stone position
                available -= 1  # update available pointer
    return rotated

# Example usage:
if __name__ == "__main__":
    box = [["#", ".", "*", "."], ["#", "#", "*", "."]]
    result = rotateTheBox(box)
    for row in result:
        print(row)