Abstract / Summary

Rotate a box of balls to make each row have the same number of balls using a limited number of rotations.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 83% (300k+ submissions).

Typical patterns to solve this problem:

• Array
• Matrix
• Two Pointers

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided implementation solves the problem of rotating a rectangular box 90 degrees clockwise while allowing stones (#) to fall under gravity and respecting immovable obstacles (*). The algorithm constructs a new matrix that represents the rotated configuration, iterates through the original matrix in a specific order to simulate rotation, and places obstacles and stones accordingly. The code is organized into three logical phases: preparation of the output grid, traversal of the input grid with coordinate transformation, and placement of elements respecting the physical constraints of the problem.

Preparation of the Result Grid

The first part of the function allocates the output structure. The width of the original box becomes the height of the rotated box, and the height becomes the width. A nested loop fills the result with placeholder dots (.) that denote empty cells.

result = []

# layout of the rotated box
width  = len(box)
height = len(box[0])
for y in range(height):
    result.append([ "." ] * width)

By pre-filling the grid with dots, later steps can safely assume that any cell not explicitly overwritten remains empty, simplifying the logic for stone placement.

Main Traversal and Coordinate Mapping

The core of the algorithm consists of a double loop. The outer loop iterates over the original rows (x), while the inner loop walks the columns (y) in reverse order. Two coordinate transformations are applied:

• y2 = width - x - 1 computes the row index in the original box that maps to the current column after rotation.
• x2 = y computes the column index in the original box that maps to the current row after rotation.

These calculations implement a 90-degree clockwise rotation without creating an intermediate transposed matrix.

for x in range(width):
    # rotate
    y2  = width - x - 1

    # next free cell
    pos = height - 1

    for y in reversed(range(height)):
        # rotate
        x2 = y
        ...

The variable pos tracks the lowest available empty cell in the current column of the result grid, enabling stones to “fall” to the correct location.

Handling Obstacles

When the algorithm encounters an obstacle (*) in the original box, it directly copies the obstacle to the corresponding rotated position. The presence of an obstacle also resets the pos pointer to the cell just above the obstacle, ensuring that subsequent stones cannot pass through it.

if box[y2][x2] == "*":
    result[y][x] = "*"
    pos = y - 1

This logic guarantees that obstacles remain fixed after rotation and that they correctly block the vertical movement of stones.

Dropping Stones

For each stone (#) encountered, the algorithm searches upward from the current pos until it finds an empty cell (.) in the result grid. Once found, the stone is placed there, and the pos pointer is left unchanged, allowing the next stone in the same column to settle directly above the previous one.

if box[y2][x2] == "#":
    # look for empty cell
    while result[pos][x] != ".":
        pos -= 1
    result[pos][x] = "#"

Because the inner loop processes rows from bottom to top (via reversed(range(height))), stones are handled in the order they would naturally fall, and the while-loop ensures they occupy the lowest possible empty slot.

Edge Cases Managed by the Code

The implementation gracefully handles several boundary conditions:

• Boxes with a single row or column are correctly rotated because the width and height calculations are derived directly from the input dimensions, and the loops adapt to those sizes.
• Empty rows or columns (containing only .) result in a rotated grid filled entirely with . because the placement logic never modifies those cells.
• Multiple consecutive obstacles are supported; each obstacle updates pos to the cell above it, preventing stones from crossing any of the obstacles.
• When a stone appears directly above an obstacle in the original orientation, the rotation logic places the obstacle first, then the stone settles just above it, mirroring the expected physical behavior.

Performance Optimizations Observed

The algorithm avoids the creation of auxiliary matrices for intermediate rotations. By computing the rotated coordinates on the fly, it reduces memory overhead to a single result grid plus a few scalar variables. The use of a pre-filled result grid eliminates the need for repeated boundary checks when searching for empty cells; the while-loop only inspects already allocated cells. Additionally, the pos pointer is reused for each column, eliminating the need for a fresh scan of the entire column for every stone, which cuts down on redundant work.

Overall, the code delivers a concise solution that leverages in-place coordinate transformation and a single pass over the input data to achieve the desired rotated and gravity-settled configuration.

Imagine you have a big box filled with heavy toy blocks named stones, immovable walls, and empty spaces. You want to tip the box onto its side so that everything falls down, just like playing with a puzzle.

First, get a new empty box that is the right shape for when it stands on its side. Since the box is tipping over, the parts that were on the bottom now form the vertical side.

Next, look at each column of the original box. Because the box is rotating, move from the bottom to the top for each one. If there is a wall, it stays exactly where it lands. If you see a stone, it starts to fall. It tumbles down to the bottom of the container, but it stops if it hits a wall or another stone that already landed. The empty spaces simply get filled in as the stones keep finding their way down until they have nowhere left to go. Each stone finds its own cozy spot at the bottom of the new grid.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: polynomial
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++	Python			Java				TS
	WalkCCC	C++	Python			Java
	leetcode.ca	C++	Python			Java		Go	Rust	TS
	Progiez	C++	Python			Java
github	black-shadows	C++
	charles-wangkai					Java
	everthis			JS
	fsq	C++
	haoel	C++
	JoshCrozier			JS
	lkwq007		Python
	martianoff				Scala
	suxrobGM						C#
	trung-hn		Python
	wisdompeak	C++
	withaarzoo	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python, Rust, TypeScript
Progiez	C++, Java, Python
black-shadows	C++, C++
charles-wangkai	Java
everthis	JavaScript
fsq	C++
haoel	C++
JoshCrozier	JavaScript
lkwq007	Python
martianoff	Scala
suxrobGM	C#
trung-hn	Python
wisdompeak	C++
withaarzoo	C++

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality