The problem
Balloons have numbers. Popping balloon i earns left × i × right, using its current neighbours (a missing neighbour counts as 1). Pop all balloons in the order that earns the most coins.
Input: [3, 1, 5, 8] Output: 167
Picture it
Picture a row of balloons with an unpoppable 1-balloon at each end. Thinking about which balloon pops first is messy, because neighbours keep changing. Instead, for each stretch, choose which balloon pops last: at that moment its neighbours are the stretch’s fixed ends, and the left and right parts can be solved independently.
How to recognise it
- You remove items from a row, and the score of each removal depends on its current neighbours, which change as items disappear.
- The final answer is the best over all orders of removal.
- Thinking about the first removal is messy, because it changes the neighbours of everything else.
- Thinking about the last item removed in a stretch makes the two sides independent.
- Up to 300 items allows an O(n³) solution but rules out trying orders.
Start with brute force
Try every item as the next one to pop, score it with its current neighbours, and recurse on the remaining row.
from functools import lru_cache
def burst_brute(nums):
@lru_cache(None)
def go(row): # row is a tuple of balloons still alive
best = 0
for i in range(len(row)):
left = row[i - 1] if i > 0 else 1
right = row[i + 1] if i + 1 < len(row) else 1
best = max(best, left * row[i] * right + go(row[:i] + row[i + 1:]))
return best
return go(tuple(nums))
Without the cache there are n! pop orders (10! is already 3.6 million). Even with the cache there is one state for each subset of balloons that are still alive, so up to 2^n states. For n = 300 neither is possible.
From brute force to the idea
- Find the problem. If you choose the first balloon to pop in a stretch, the stretch splits into two parts that still affect each other: popping a balloon changes the neighbour of the balloons next to it.
- Flip the question. Choose the last balloon
kto pop between two fixed boundarieslandr. Whenkis popped last, everything else strictly betweenlandris already gone, so its neighbours are exactlyb[l]andb[r]. Its score isb[l] * b[k] * b[r]. - The two sides split cleanly. Balloons between
landkand betweenkandrare popped beforek, and each side only seeskand its own boundary, so the two sides are independent:best[l][k] + best[k][r]. - Pad the row.
b = [1] + nums + [1]adds imaginary 1-balloons that are never popped, so the edges need no special cases. - Fill by gap size.
best[l][r]is the best score for popping everything strictly betweenlandr. A pair at distancegapneeds only smaller gaps, so the loops go from gap 2 upwards. The answer isbest[0][n-1].
This is the key idea: choose the last balloon in each stretch, and the sides become separate smaller problems.
The key idea
Interval DP: dp[l][r] = max over k of dp[l][k] + dp[k][r] + v[l]·v[k]·v[r]. O(n³).
Python solution
def max_coins(nums):
b = [1] + nums + [1] # imaginary 1-balloons at the ends
n = len(b)
best = [[0] * n for _ in range(n)] # best[l][r]: pop everything strictly between
for gap in range(2, n):
for l in range(n - gap):
r = l + gap
for k in range(l + 1, r): # k is the LAST balloon popped in (l, r)
best[l][r] = max(best[l][r],
best[l][k] + b[l] * b[k] * b[r] + best[k][r])
return best[0][n - 1]In the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.
Complexity
| Approach | Time | Space |
|---|---|---|
| Brute force | O(n!) without the cache; up to O(2^n · n) with it | O(2^n): one cached value per subset |
| Interval DP (shown code) | O(n³): about n²/2 pairs (l, r), each trying up to n values of k, roughly n³/6 steps in total | O(n²): the table |
For n = 300 that is about 4.5 million inner steps, which takes around a second in Python.
Edge cases
- Empty list: the loops do nothing and the code returns 0.
- One balloon (
[7]): returns 7, since both neighbours are the imaginary 1s. - Two balloons (
[1, 5]): returns 10 (pop 1 first for 5, then 5 for 5). - Zeros:
[0]and[0, 0]both return 0, and a zero in the middle simply scores nothing when popped. - Equal values (
[2, 2, 2]): returns 14. - The padding: without the two 1s,
[3, 1, 5, 8]gives 135, not 167.
Common mistakes
- Choosing the first balloon to pop in each stretch, which does not split the problem into independent sides.
- Popping the smallest balloon first, a plausible greedy that gives 78 on
[3, 1, 5, 8]instead of 167. - Letting
krun overrange(l, r + 1)instead ofrange(l + 1, r), which scores the boundaries as if they were popped. - Forgetting the padding, so edge balloons lose a neighbour.
A stick of length n is cut at the given positions. Each cut costs the length of the piece being cut. Find the cheapest total cost, choosing the order of cuts. For n = 7 and cuts [1, 3, 4, 5] the answer is 16. Describe your approach, then write it if you like.
Compare with our answer
Same interval shape: add the two ends to the cut positions, and for each stretch choose which cut is made first. Its cost is the stretch length, and the two sides are then independent.
def min_cut_cost(n, cuts):
c = [0] + sorted(cuts) + [n]
m = len(c)
cost = [[0] * m for _ in range(m)]
for gap in range(2, m):
for l in range(m - gap):
r = l + gap
cost[l][r] = min(cost[l][k] + cost[k][r]
for k in range(l + 1, r)) + c[r] - c[l]
return cost[0][m - 1]
It gives 16 for the example, 22 for n = 9 with cuts [5, 6, 1, 4, 2], and 0 when there are no cuts. Time O(m³), space O(m²).
A strong answer mentions: adding the ends, minimising instead of maximising, and choosing the first cut here because the cost depends on the whole piece.
1. You may split a row of items into stretches, and removing an item scores according to its current neighbours. Which idea usually splits the problem into independent parts?
When an item is removed last, its neighbours are the stretch ends, so the two sides can be solved on their own. A greedy rule such as "smallest first" gives 78 on [3, 1, 5, 8], not 167.
2. Why is the shown code O(n³) rather than O(n!)?
The table has one entry per pair (l, r) and each entry loops over k once. Nothing is skipped and not only the largest balloon is tried.
3. A learner changes the innermost loop to for k in range(l, r + 1). What does max_coins([3, 1, 5, 8]) return?
With k at l or r the code adds b[l] * b[k] * b[r] for a balloon that is never popped, and reuses the entry being computed. Running the variant gives 529 where the right answer is 167.
Score 60% or more and the lesson is marked complete.