Skip to main content
Talentd

Rotating the Box - Solution & Explanation

MediumArrayTwo PointersMatrix9 min readAsked at: Amazon, Microsoft, Meta +7
Practice this problem

Problem Statement

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

Approach Overview

Problem Overview: You receive an m x n box represented as a matrix containing stones (#), obstacles (*), and empty spaces (.). Stones fall to the right due to gravity until blocked by an obstacle or another stone. After gravity settles, the entire box is rotated 90 degrees clockwise. The task is to return the final matrix.

Approach 1: Simulate Gravity and Then Rotate (Time: O(mn), Space: O(mn))

Process each row independently and simulate gravity before rotation. Scan from right to left using a pointer that marks the next position where a stone can settle. When you encounter a stone (#), move it to the pointer position and decrement the pointer. When an obstacle (*) appears, reset the pointer to the cell just left of the obstacle since stones cannot pass through it. After all rows stabilize, construct the rotated matrix by mapping box[r][c] to result[c][m-1-r]. This approach cleanly separates physics (gravity) from geometry (rotation) and is easy to reason about. It relies on sequential traversal of the array and basic matrix transformation.

Approach 2: Transpose and Simulate Gravity Directly (Time: O(mn), Space: O(mn))

Instead of settling stones first, rotate the matrix structure immediately and simulate gravity afterward. Build the rotated matrix using the same coordinate transform rotated[c][m-1-r] = box[r][c]. After rotation, gravity acts downward rather than to the right. Process each column using a two-pointer technique: scan upward while maintaining a pointer where the next falling stone should land. Obstacles reset the pointer just above them, while stones move down to the pointer location. This uses the classic two pointers pattern to compact stones within segments separated by obstacles.

Recommended for interviews: The gravity-first simulation is usually easier to explain and implement during interviews. You demonstrate understanding of constrained movement using pointers and then apply a standard matrix rotation. The transpose-first approach is equally optimal but slightly less intuitive because gravity changes direction after rotation. Showing either solution with clear reasoning and O(mn) complexity is typically what interviewers expect.

Approach 1: Simulate Gravity and Then Rotate

In this approach, first simulate the effect of gravity on the stones in the box before rotating the box 90 degrees clockwise. To simulate gravity, traverse each row from right to left, moving stones to the right until they hit an obstacle or stack upon other stones. Once every stone has settled due to gravity, create a new matrix representing the rotated box by converting rows into columns.

This Python solution iterates through each row of the box matrix from right to left, simulating the effect of gravity by moving stones ('#') to the rightmost available positions and stopping if an obstacle ('*') is encountered. After gravity is applied, the matrix is transposed to achieve a 90 degrees clockwise rotation.

Code

PythonC++

Python

C++

Complexity

Time Complexity: O(m * n), where m is the number of rows and n is the number of columns in the matrix. This complexity comes from the need to process each element when simulating gravity and then again when transposing.
Space Complexity: O(1) if we ignore the space for the output result that is unavoidable for transposing the matrix.

Try this approach in the editor →

Approach 2: Transpose and Simulate Gravity Directly

This approach creates a new matrix to represent the rotated version of the box. After initializing the new transposed matrix, simulate the gravitational fall of each stone by placing them in the correct positions in the new matrix. This is achieved by iterating through the rotated columns and calculating the final position of each stone.

The Java solution pre-allocates a rotated matrix, initializes it with empty spaces, and directly simulates the effects of gravity as each stone is repositioned in the rotated matrix. This approach eliminates the need for a separate gravity simulation phase before rotation.

Code

JavaJavaScript

Java

JavaScript

Complexity

Time Complexity: O(m * n) because transposing and simulating stone drops require us to iterate through all elements.
Space Complexity: O(m * n) for storing the rotated matrix.

Try this approach in the editor →

Approach 3: Queue Simulation

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

The time complexity is O(m times n), and the space complexity is O(m times n). Where m and n are the number of rows and columns of the matrix, respectively.

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Simulate Gravity and Then Rotate

Time Complexity: O(m * n), where m is the number of rows and n is the number of columns in the matrix. This complexity comes from the need to process each element when simulating gravity and then again when transposing.
Space Complexity: O(1) if we ignore the space for the output result that is unavoidable for transposing the matrix.

Transpose and Simulate Gravity Directly

Time Complexity: O(m * n) because transposing and simulating stone drops require us to iterate through all elements.
Space Complexity: O(m * n) for storing the rotated matrix.

Queue Simulation—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Simulate Gravity Then RotateO(mn)O(mn)Most intuitive approach. Easy to explain during interviews and separates gravity simulation from rotation.
Transpose Then Simulate GravityO(mn)O(mn)Useful when you prefer working with the final rotated structure and applying gravity vertically with two pointers.

Video Solution

Rotating the Box - Leetcode 1861 - Python • NeetCodeIO • 13,770 views views

Watch 9 more video solutions →

Frequently Asked Questions

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.

Ready to solve this problem?

Practice Rotating the Box with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays