#1861

Medium

auto_awesomeTwo-pointer scanning with invariant tracking

LeetCode Problem Workspace

Rotating the Box

Rotate a box represented by a character matrix, letting stones fall under gravity using precise two-pointer scanning and invariant tracking.

array two pointers matrix

Problem Statement

You are given an m x n matrix representing a side view of a box. Each cell contains either a stone '#', an obstacle '*', or empty space '.'. When the box rotates 90 degrees clockwise, stones will fall vertically until blocked by another stone, an obstacle, or the bottom of the box. Obstacles stay in place and stones cannot move horizontally beyond their column.

Return the final state of the box after rotation and stone falling. Each stone must occupy the lowest possible position in its column post-rotation. Implement this efficiently using a two-pointer approach to track empty positions versus stones per row.

Examples

Example 1

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

Output: [["."], ["#"], ["#"]]

Example details omitted.

Example 2

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

Output: [["#","."], ["#","#"], ["*","*"], [".","."]]

Example details omitted.

Example 3

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

Output: [[".","#","#"], [".","#","#"], ["#","#","*"], ["#","*","."], ["#",".","*"], ["#",".","."]]

Example details omitted.

Constraints

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

Solution Approach

Rotate Box Mapping

Create a new matrix for the rotated box with dimensions n x m. Map each element from the original box using rotatedBox[i][j] = box[m - 1 - j][i]. This ensures the 90-degree clockwise rotation is correctly applied before handling gravity.

Two-Pointer Gravity Simulation

Iterate each row of the original box from right to left. Use two pointers: one for the next empty space where a stone can fall, and one scanning stones. Move stones towards the next available space, skipping obstacles. This maintains the invariant that stones only fall vertically and never pass obstacles.

Construct Final Rotated Box

After simulating stone falling per row, insert the updated stones and obstacles into the rotated box matrix. Each rotated position now reflects stones at the correct lower positions and obstacles fixed in place.

Complexity Analysis

Metric	Value
Time	O(m \times n)
Space	O(m \times n)

Time complexity is O(m \times n) because every cell is scanned once for rotation and once for gravity simulation. Space complexity is O(m \times n) for storing the rotated box matrix separate from the original grid.

What Interviewers Usually Probe

Are you tracking empty spaces and obstacles efficiently per row?
Can you explain how rotatedBox[i][j] = box[m - 1 - j][i] ensures correct clockwise rotation?
Do you understand why two pointers are needed instead of moving stones one by one?

Common Pitfalls or Variants

Common pitfalls

Forgetting to reset the empty-space pointer after an obstacle in a row, causing incorrect stone placement.
Rotating before simulating gravity can produce wrong final positions.
Using nested loops per stone without two-pointer scanning can exceed O(m*n) time and fail for large grids.

Follow-up variants

Rotate counterclockwise with similar gravity rules, adjusting indices accordingly.
Allow diagonal gravity where stones can slide to lower adjacent empty cells.
Change obstacles to movable blocks that can fall, requiring different invariant tracking.

FAQ

What is the core pattern for Rotating the Box?

The problem uses two-pointer scanning with invariant tracking per row to simulate stones falling under gravity after rotation.

How do I rotate a matrix 90 degrees clockwise?

Use the mapping rotatedBox[i][j] = box[m - 1 - j][i] to transform the original box positions correctly.

Can obstacles move during the rotation?

No, obstacles remain fixed in their original positions and only stones fall due to gravity.

Why use two pointers instead of single iteration?

Two pointers allow tracking empty spaces and stones efficiently per row, preventing overwriting stones and reducing complexity to O(m*n).

What if the box has maximum size 500x500?

The two-pointer approach ensures O(m*n) time complexity, making it feasible to handle large grids within constraints.

terminal

Solution

Solution 1: Queue Simulation

First, we rotate the matrix 90 degrees clockwise, then simulate the falling process of the stones in each column.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

class Solution:
    def rotateTheBox(self, box: List[List[str]]) -> List[List[str]]:
        m, n = len(box), len(box[0])
        ans = [[None] * m for _ in range(n)]
        for i in range(m):
            for j in range(n):
                ans[j][m - i - 1] = box[i][j]
        for j in range(m):
            q = deque()
            for i in range(n - 1, -1, -1):
                if ans[i][j] == '*':
                    q.clear()
                elif ans[i][j] == '.':
                    q.append(i)
                elif q:
                    ans[q.popleft()][j] = '#'
                    ans[i][j] = '.'
                    q.append(i)
        return ans

Continue Practicing

#2503 maximum number of points from grid queries #1855 maximum distance between a pair of values #1877 minimize maximum pair sum in array