Abstract / Summary

A ball drops through a grid with bumpers find where it exits the bottom edge.

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 72% (200k+ submissions).

Typical patterns to solve this problem:

• Array
• Matrix
• Simulation

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 classic “ball dropping” problem on a rectangular grid where each cell contains either 1 (redirect right) or -1 (redirect left). A ball is released from each column at the top of the grid and follows the direction indicated by the current cell. The algorithm determines the final column index where each ball exits the bottom of the grid, or -1 if the ball gets stuck or leaves the grid laterally.

The solution is expressed as a generator that yields a result for each starting column. The outer loop iterates over all possible entry columns, while the inner loop simulates the ball’s path row by row.

Key Steps

The first step extracts the dimensions of the grid.

height = len(grid)
width  = len(grid[0])

The outer loop selects each starting column.

for i in range(width):
    x = i

Inside the outer loop, the inner loop processes each row from top to bottom.

for y in range(height):
    cell = grid[y][x]
    x   += cell

After moving the ball horizontally according to the current cell, the algorithm checks for three termination conditions.

• Out-of-bounds detection:

if x < 0 or x >= width:
    yield -1  # out of bounds
    break

• “V” shape detection where adjacent cells form a trap:

if grid[y][x] != cell:
    yield -1  # stuck in a "V"
    break

• Successful arrival at the bottom row:

if y == height - 1:
    yield x  # reached bottom

Each yield produces the result for the current starting column before the outer loop proceeds to the next column.

Edge Cases Handled

The code explicitly handles the situation where a ball would move outside the leftmost or rightmost column. By checking x < 0 and x >= width immediately after the horizontal shift, it prevents index errors and correctly reports a failure with -1.

A second edge case is the formation of a “V” shape, where two adjacent cells point toward each other (e.g., a 1 followed by a -1). In such a configuration the ball cannot pass through the junction. The condition grid[y][x] != cell detects this mismatch after the ball has moved horizontally, ensuring that the ball is marked as stuck.

The algorithm also correctly handles the trivial case of a single-row grid. The inner loop runs once, and the bottom-row check y == height - 1 yields the final column directly if the ball does not encounter an out-of-bounds or “V” condition.

Performance Optimizations

The implementation avoids the allocation of auxiliary data structures for each ball’s trajectory. By reusing the variable x for the current column position and updating it in place, the algorithm maintains a minimal memory footprint.

The use of a generator (yield) allows the caller to consume results lazily, which can be advantageous when only a subset of the outcomes is needed. This approach eliminates the need to store the entire result list in memory before returning.

The inner loop terminates early as soon as a terminating condition is met (break after a yield). This early exit prevents unnecessary iteration over remaining rows once the ball’s fate is decided, reducing the total number of cell accesses.

Overall, the code follows a straightforward simulation strategy that processes each cell at most once per ball, delivering an efficient solution within the constraints of the problem.

Imagine a board that looks like a tall grid where each square has a little wooden plank leaning either to the left or to the right. A tiny ball starts at the very top of each column and wants to roll all the way down to the bottom.

When the ball hits a plank, it slides in the direction the plank is pointing. If the plank leans right, the ball moves right. If it leans left, the ball moves left. As the ball rolls, it passes through many rows of these planks.

Sometimes, the ball might roll off the edge of the board, which is like dropping off the side of a table. Other times, the ball gets stuck. This happens if the ball slides into a corner where two planks are pointing at each other like a little letter V, trapping the ball in a tight spot from which it cannot escape.

The code keeps track of where the ball is by looking at its column position. For every column at the top, the code follows the ball row by row. It updates the ball's position based on which way the hidden plank is leaning. If the ball stays safe and keeps sliding until it finishes all the rows, the code remembers which column the ball ended up in at the very bottom. If the ball falls off the side or gets stuck, the code marks that path as impossible.

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	JS	Java					Go	Rust	TS
	Progiez	C++	Python		Java
github	AdelDaniel							Dart
	black-shadows	C++
	charles-wangkai				Java
	everthis			JS
	fartem					Ruby
	fsq	C++
	JoshCrozier			JS
	lkwq007		Python
	suxrobGM								C#
	trung-hn		Python
	vthwang				Java
	wisdompeak	C++
	yuanliu666						Kotlin
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, JavaScript, Python, Rust, TypeScript
Progiez	C++, Java, Python
AdelDaniel	Dart
black-shadows	C++, C++
charles-wangkai	Java
everthis	JavaScript
fartem	Ruby
fsq	C++
JoshCrozier	JavaScript
lkwq007	Python
suxrobGM	C#
trung-hn	Python
vthwang	Java
wisdompeak	C++
yuanliu666	Kotlin

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