Abstract / Summary

Given a row of balloons with numbers, find the maximum coins by bursting them one at a time with specific rules.

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 63% (600k+ submissions).

Typical patterns to solve this problem:

• Array
• Dynamic Programming

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 “burst balloons” dynamic-programming problem. It transforms the input list by inserting sentinel values of 1 at both ends, which eliminates the need for special-case handling when a balloon at the original boundary is burst. The core of the algorithm is a recursive function deeper that explores every possible choice for the last balloon to burst within a sub-interval defined by two indices. Memoization, achieved through the @cache decorator, ensures that each sub-interval is evaluated only once, turning an exponential search space into a tractable computation.

Key Steps

Extending the Input with Sentinels

nums = [1] + nums + [1]

By surrounding the original array with 1s, the algorithm can treat every balloon uniformly. When the leftmost or rightmost original balloon is considered, the multiplication with the sentinel 1 correctly reflects the problem’s rule that non-existent neighbors contribute a factor of 1. This eliminates conditional checks for array bounds throughout the recursion.

Defining the Memoized Recursive Helper

@cache
def deeper(left, right):
    if left == right:
        return nums[left]
    ...

The helper receives the indices of the current interval’s boundaries, which are inclusive for the sentinel values but exclusive for the balloons that can be burst inside. The base case left == right occurs when the interval collapses to a single sentinel; the function returns the sentinel’s value, which is 1. This base case also implicitly handles intervals that contain no burstable balloons, because the loop that follows will not execute.

Enumerating the Last Balloon to Burst

last = 0
for i in range(left + 1, right):
    coins = nums[left] * nums[i] * nums[right]
    last = max(last, deeper(left, i) + coins + deeper(i, right))
return last

The loop iterates over every index i that lies strictly between left and right. For each candidate i, the algorithm computes the coins obtained by bursting balloon i last in the current interval: the product of the values at the two current boundaries and the balloon itself. The total for this choice is the sum of three parts:

1. The optimal result for the left sub-interval [left, i].
2. The coins earned by bursting i last.
3. The optimal result for the right sub-interval [i, right].

The maximum over all candidates is stored in last and returned. Because deeper is cached, the results of the left and right sub-intervals are retrieved instantly on subsequent calls.

Initiating the Computation

return deeper(0, len(nums) - 1)

The initial call spans the entire extended array, from the first sentinel at index 0 to the last sentinel at index len(nums) - 1. The recursion then systematically breaks down the problem into smaller intervals until reaching the base case.

Edge Cases Handled

The sentinel insertion directly addresses scenarios where the original list is empty or contains a single element. An empty input becomes [1, 1]; the recursive call receives left = 0 and right = 1. The loop range range(left + 1, right) yields no iterations, so last remains 0 and the function returns 0, which is the correct maximum coin count for an empty set of balloons.

When the original list has one element, say [5], the extended list is [1, 5, 1]. The recursive call deeper(0, 2) iterates with i = 1 only. The computed coins equals 1 * 5 * 1 = 5, and both recursive sub-calls hit the base case, returning 1 each. The total becomes 1 + 5 + 1 = 7, but because the base case returns the sentinel value itself, the final result after the max operation correctly yields 5, matching the expected outcome for a single balloon.

Performance Optimizations

The most significant optimization is the use of the @cache decorator from the functools module. By memoizing the results of deeper(left, right), the algorithm avoids recomputing identical sub-problems that arise from different recursion paths. This transforms the naive exponential recursion into a dynamic-programming solution whose runtime grows polynomially with the number of balloons.

Another subtle optimization stems from the choice of interval representation. By defining intervals with inclusive boundaries and iterating only over interior indices, the algorithm reduces the number of recursive calls compared to a formulation that would need to handle open intervals or additional boundary checks. The sentinel values also prevent the need for conditional multiplication by 1 inside the loop, keeping the inner computation lightweight.

Overall, the combination of sentinel augmentation and memoization yields a solution that efficiently explores the combinatorial space of burst orders while maintaining clear and concise code structure.

Imagine you have a row of colorful balloons, each with a number written on it. When you pop a balloon, you get a prize based on its number and the numbers of its neighbors. The goal is to pop them all one by one in an order that gets the biggest total prize possible.

This code works like a clever detective looking into the future. It starts by adding two invisible balloons filled with the number one at the very beginning and the very end of the row. These help so that even when a balloon is all by itself, it still has neighbors to multiply with.

The function named deeper is the heart of the puzzle. It pretends to look at a small group of balloons and asks which one should be the very last one popped in that group. By imagining popping one balloon last, it breaks the big row into two smaller rows of balloons. It then solves the puzzle for those smaller groups and adds everything together.

Because there are many ways to choose which balloon is popped last, it tries every single possibility to see which path gives the most coins. The special cache part is like a magical notebook. Every time the code figures out the best score for a specific group of balloons, it writes the answer down. If it ever sees that same group of balloons again, it just checks its notebook instead of doing the hard work all over again. This makes the computer very fast at finding the best way to pop every balloon in the row.

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++		Rust	Python		Java		Go	TS
	LeetcodeHelp	C++			Python		Java
	MemoryLimitExceeded	C++			Python
	Progiez	C++			Python		Java
github	aylei			Rust
	BigEggStudy		C#
	black-shadows	C++
	charles-wangkai						Java
	chenyanzhe	C++
	everthis					JS
	FelixFan1122		C#
	gouthampradhan						Java
	haoel	C++
	JoshCrozier					JS
	keineahnung2345	C++
	linouk23	C++
	MacJim	C++
	ruoru			Rust
	suxrobGM		C#
	trung-hn				Python
	wisdompeak				Python
	XiaotaoGuo	C++
	yuanliu666							Kotlin
	zfang399	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python, Rust, TypeScript
LeetcodeHelp	C++, Java, Python
MemoryLimitExceeded	Python, C++
Progiez	C++, Java, Python
aylei	Rust
BigEggStudy	C#
black-shadows	C++, C++
charles-wangkai	Java
chenyanzhe	C++
everthis	JavaScript
FelixFan1122	C#
gouthampradhan	Java
haoel	C++
JoshCrozier	JavaScript
keineahnung2345	C++
linouk23	C++
MacJim	C++
ruoru	Rust
suxrobGM	C#
trung-hn	Python
wisdompeak	Python
XiaotaoGuo	C++
yuanliu666	Kotlin
zfang399	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