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
- A 90-degree clockwise rotation maps original cell
(i, j)to new cell(j, m - 1 - i), producing ann x mgrid. - After the rotation, gravity acts downward, i.e. toward larger row indices.
- Simulate the fall per column with a single backward pass, tracking the lowest empty row
empty. - On encountering a stone, move it to row
emptyand decrementempty; on encountering an obstacle, resetemptytoi - 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
emptyincorrectly at an obstacle: it must becomei - 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.