{x}
blog image

Rotating the Box

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.

 

Example 1:

Input: boxGrid = [["#",".","#"]]
Output: [["."],
         ["#"],
         ["#"]]

Example 2:

Input: boxGrid = [["#",".","*","."],
              ["#","#","*","."]]
Output: [["#","."],
         ["#","#"],
         ["*","*"],
         [".","."]]

Example 3:

Input: boxGrid = [["#","#","*",".","*","."],
              ["#","#","#","*",".","."],
              ["#","#","#",".","#","."]]
Output: [[".","#","#"],
         [".","#","#"],
         ["#","#","*"],
         ["#","*","."],
         ["#",".","*"],
         ["#",".","."]]

 

Constraints:

  • m == boxGrid.length
  • n == boxGrid[i].length
  • 1 <= m, n <= 500
  • boxGrid[i][j] is either '#', '*', or '.'.

Solution Explanation for Rotating the Box

This problem involves rotating a matrix 90 degrees clockwise and simulating gravity on the stones within the matrix. The solution uses a two-step approach: rotation and gravity simulation.

1. Rotation:

The matrix is first rotated 90 degrees clockwise. This is achieved by transposing the matrix and then reversing each row. The original m x n matrix becomes an n x m matrix.

2. Gravity Simulation:

After rotation, gravity is simulated for each column. For each column, the solution iterates from bottom to top. A queue (q in the code) is used to track the indices of empty cells (.) where stones can fall.

  • When an obstacle (*) is encountered, the queue is cleared because stones cannot fall past obstacles.
  • When an empty cell (.) is encountered, its index is added to the queue.
  • When a stone (#) is encountered and the queue is not empty, it means the stone can fall. The index of the topmost empty cell from the queue is taken, the stone is moved to that empty cell, and the current cell becomes empty. The stone's index is then added to the queue.

This process ensures that each stone falls to the lowest possible position in its column before landing on an obstacle or another stone.

Time Complexity Analysis:

  • Rotation: The rotation process takes O(m*n) time, as each element in the matrix is accessed and moved once.
  • Gravity Simulation: The gravity simulation iterates through each column once. For each column, it iterates through the cells from bottom to top. In the worst case, each cell is visited once, making the time complexity O(m*n).

Therefore, the overall time complexity is O(m*n), dominated by the rotation and gravity simulation steps.

Space Complexity Analysis:

  • The rotated matrix ans requires O(m*n) space.
  • The queue q used in gravity simulation requires O(min(m,n)) space in the worst case (a column filled with empty cells before the obstacle).

Therefore, the overall space complexity is O(m*n), dominated by the space used for the rotated matrix.

Code Examples (Python, Java, C++, Go):

The provided code examples demonstrate the solution. All versions follow the same algorithm: first rotate the box, then simulate gravity in each column using a queue to track empty spaces. The languages vary slightly in their queue implementations (e.g., deque in Python, ArrayDeque in Java, queue in C++, and slices in Go) but the core logic remains consistent. The comments in the code help trace the steps of both rotation and gravity simulation.