⚡Flashcard Drill➔
NeetCode #923LC-1861MediumMath & Geometry
← Back to All Problems

#923 · #1861 · Rotating the Box(旋转盒子)

📌 Problem Statement & Constraints

Given an m x n box represented by a grid of characters, where # is a stone, * is a fixed obstacle and . is empty, rotate the box 90 degrees clockwise so that it becomes n x m, then let gravity pull every stone down until it rests on the floor or on an obstacle. Return the resulting grid. Constraints: 1 <= m, n <= 500, and each cell is one of #, *, ..

💡 Core Algorithmic Approaches

  1. A 90-degree clockwise rotation maps original cell (i, j) to new cell (j, m - 1 - i), producing an n x m grid.
  2. After the rotation, gravity acts downward, i.e. toward larger row indices.
  3. Simulate the fall per column with a single backward pass, tracking the lowest empty row empty.
  4. On encountering a stone, move it to row empty and decrement empty; on encountering an obstacle, reset empty to i - 1, the row directly above it.

💻 Benchmark Python3 Implementation

class Solution:
    def rotateTheBox(self, boxGrid: List[List[str]]) -> List[List[str]]:
        m, n = len(boxGrid), len(boxGrid[0])
        # rotate 90 degrees clockwise: (i, j) -> (j, m - 1 - i)
        res = [["."] * m for _ in range(n)]
        for i in range(m):
            for j in range(n):
                res[j][m - 1 - i] = boxGrid[i][j]
        # gravity: stones fall toward larger row indices within each column
        for j in range(m):
            empty = n - 1
            for i in range(n - 1, -1, -1):
                if res[i][j] == "#":
                    res[i][j] = "."
                    res[empty][j] = "#"
                    empty -= 1
                elif res[i][j] == "*":
                    empty = i - 1            # stones cannot pass the obstacle
        return res

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(m * n): the rotation and the gravity pass are each linear in the number of cells.
💾 Space Complexity
O(m * n): the rotated result grid.

⚠️ Interview Pitfalls & Follow-ups

  • Applying gravity before rotating: the direction of gravity differs between the two orientations, so the rotation must come first.
  • Resetting empty incorrectly at an obstacle: it must become i - 1, the row directly above the obstacle.
  • Moving stones upward: gravity pulls them toward the largest available row index.
  • Leaving the source cell occupied: the stone must be cleared from its old position, otherwise it is duplicated.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Math & Geometry Problems