How do you solve Rotating the Box on LeetCode?

Rotating the Box (LeetCode #1861) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(n) space complexity. Key insight: Gravity only affects stones, not obstacles.

What is the brute force solution for Rotating the Box?

The brute force approach for Rotating the Box is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute force approach involves creating a new matrix for the rotated box and then manually placing stones and obstacles based on their positions in the original matrix. This method is straightforward but not efficient. The optimal Optimal Solution approach improves this to O(n).

What algorithm or data structure is used to solve Rotating the Box?

Rotating the Box uses the following concepts: Array, Two Pointers, Matrix. The recommended patterns to study are: Two Pointers, Matrix.

What are the interview tips for Rotating the Box?

Think about how gravity affects the stones. Visualize the rotation process step by step. Practice similar problems to get comfortable with matrix manipulations.

What are common mistakes when solving Rotating the Box?

Not correctly handling the index for stones and obstacles. Confusing the dimensions of the rotated matrix.

#1861

Rotating the Box

Medium

ArrayTwo PointersMatrixTwo PointersMatrix

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n)
Space	O(1)	O(n)

💡

Intuition

Time O(n)Space O(n)

The optimal solution leverages a single pass through the box to determine where stones should fall after rotation. By using a two-pointer technique, we can efficiently manage the positions of stones and obstacles.

⚙️

Algorithm

3 steps

1Step 1: Create a new matrix of size n x m to hold the rotated result.
2Step 2: Iterate through each column of the original matrix from bottom to top.
3Step 3: Use a pointer to track the position where the next stone should fall in the rotated matrix.

solution.py14 lines

1def rotateTheBox(boxGrid):
2    m, n = len(boxGrid), len(boxGrid[0])
3    rotatedBox = [['.' for _ in range(m)] for _ in range(n)]
4    for j in range(n):
5        idx = m - 1
6        for i in range(m - 1, -1, -1):
7            if boxGrid[i][j] == '#':
8                rotatedBox[idx][j] = '#'
9                idx -= 1
10            elif boxGrid[i][j] == '*':
11                idx = i - 1
12        for k in range(idx, -1, -1):
13            rotatedBox[k][j] = '.'
14    return rotatedBox

ℹ

Complexity note: The time complexity is O(n) because we only traverse each column once, and the space complexity is O(n) for the new rotated matrix.

1Gravity only affects stones, not obstacles.
2The box rotation can be visualized as a column-wise transformation.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.