Is Rotating the Box easy or hard?

Rotating the Box is rated Medium because it combines two concepts: simulation of gravity with obstacles and matrix rotation. Each step individually is straightforward, but combining them correctly requires careful index handling and pointer management.

How to solve Rotating the Box in O(mn)?

Iterate through each row from right to left and use a pointer to track the next valid position for a falling stone. Obstacles reset the pointer while stones slide toward it. After gravity stabilizes the rows, rotate the matrix using the coordinate transform result[c][m-1-r] = box[r][c].

What is the best approach for Rotating the Box?

The most common approach simulates gravity for each row using a pointer that tracks where the next stone can fall, then rotates the matrix 90 degrees clockwise. This method runs in O(mn) time and O(mn) space and cleanly separates the gravity simulation from the rotation step.

What data structure is used in Rotating the Box?

The primary data structure is a 2D matrix (array). The algorithm also uses pointer variables to track the next valid position for falling stones, which is a typical two-pointer technique applied within each row or column segment.

What is the time complexity of Rotating the Box?

The optimal solution runs in O(mn) time where m is the number of rows and n is the number of columns. Each cell is processed a constant number of times during gravity simulation and matrix rotation. Space complexity is typically O(mn) for the rotated result matrix.

Rotating the Box Python or Java solution approach?

Both Python and Java implementations typically follow the same logic: simulate gravity using a pointer for each row or column, then construct the rotated matrix. The algorithm remains O(mn) regardless of language because each cell is processed a constant number of times.

Is Rotating the Box asked at Google, Amazon, or Meta?

Matrix simulation and gravity-style problems similar to Rotating the Box appear in interviews at companies like Amazon, Google, and Meta. They test matrix traversal, two-pointer techniques, and the ability to simulate constrained movement efficiently.

Description Hints 2 Solution Video 15:14

1861. Rotating the Box

Medium82.4% acceptance10 companies

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 '.'.

Asked at 10 companies

Visa Square Sig Uber Capital One Roblox

Google Amazon Microsoft Meta

Topics

Hints open one at a time

Hint 1

Rotate the box using the relation rotatedBox[i][j] = box[m - 1 - j][i].

Hint 2

Start iterating from the bottom of the box and for each empty cell check if there is any stone above it with no obstacles between them.

15:14

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
2    def rotateTheBox(self, boxGrid: List[List[str]]) -> List[List[str]]:
3        

Starter codePython 3Spaces: 4

Examples

Case 1Case 2Case 3

Input

[["#",".","#"]]

Input

[["#",".","*","."],["#","#","*","."]]

Input

[["#","#","*",".","*","."],["#","#","#","*",".","."],["#","#","#",".","#","."]]

Your code is saved on this device.Solution