DSA Burst Balloons

Burst Balloons asks for the most coins earned by bursting a row of balloons in some order. The winning question names the balloon that bursts last inside a range.

The problem

Burst Balloons asks for the most coins earned by bursting a row of balloons in some order. Bursting one balloon earns its value times the values of its two current neighbours.

The neighbours change as balloons vanish. A balloon burst late may stand next to balloons that started far away. Choosing the order is the whole problem.

The cases used in this article

cases = [
    ([3, 1, 5, 8], 167),
    ([1, 5], 10),
    ([5], 5),
    ([], 0),
]
for coins, expected in cases:
    print("balloons:", coins, "-> best coins:", expected)

The single balloon earns five, not twenty-five or zero. Imaginary balloons of value one stand at both ends of the row. They set the neighbours for the first and last real balloons.

Intuition: bursting the biggest or the smallest first both fail

One greedy idea bursts the largest balloon first, while its neighbours are still original. Another bursts the smallest first, to remove a weak multiplier. Both rules commit to an order before seeing any consequence.

A balloon's value depends on who stands beside it at burst time. Removing a neighbour early can destroy a large product later. The simulation below runs both greedy orders in full.

Two greedy orders against the best total

def simulate(coins, order_values):
    row = list(coins)
    total = 0
    steps = []
    for value in order_values:
        idx = row.index(value)
        left = row[idx - 1] if idx > 0 else 1
        right = row[idx + 1] if idx < len(row) - 1 else 1
        gain = left * value * right
        steps.append((value, gain))
        total += gain
        row.pop(idx)
    return steps, total

coins = [3, 1, 5, 8]
for name, order in [("largest first", [8, 5, 3, 1]), ("smallest first", [1, 3, 5, 8])]:
    steps, total = simulate(coins, order)
    print(name, "- steps:", steps, "- total:", total)
print("best possible total: 167")

Neither greedy order reaches even half of the best total. The winning order bursts 1, then 5, then 3, then 8. It saves the largest balloon for last, when the padded ones frame it alone.

Brute force: try every bursting order

The brute force lists every order of the balloons. A row of n balloons has n factorial orders. It simulates each order in full and keeps the best total.

Simulation is exact, so the brute force is correct. Its cost is the order count. Four balloons already produce 24 full simulations.

All orders for the main case, counted

from itertools import permutations

def total_for_order(coins, order):
    row = list(coins)
    total = 0
    for value in order:
        idx = row.index(value)
        left = row[idx - 1] if idx > 0 else 1
        right = row[idx + 1] if idx < len(row) - 1 else 1
        total += left * value * right
        row.pop(idx)
    return total

coins = [3, 1, 5, 8]
best = 0
best_order = None
tried = 0
for order in permutations(coins):
    tried += 1
    total = total_for_order(coins, order)
    if total > best:
        best = total
        best_order = order
print("orders tried:", tried)
print("best total:", best)
print("one best order:", list(best_order))

The brute force confirms the best total of 167. It also shows the shape of the disaster. A fifth balloon would multiply the order count by five.

The optimal solution: name the balloon that bursts last in a range

Padding adds a value one balloon at both ends of the row. The state table[i][j] holds the best coins from the balloons strictly between positions i and j of the padded row, with i and j themselves still unburst.

The winning question names the balloon that bursts last inside a range. That balloon bursts when only the two boundaries remain beside it, so its product is the fixed value padded[i] times padded[k] times padded[j]. Choosing it splits the range into two free parts.

The last-balloon table on every case

def burst_max(coins):
    padded = [1] + coins + [1]
    n = len(padded)
    table = [[0] * n for _ in range(n)]
    for length in range(1, len(coins) + 1):
        for i in range(n - length - 1):
            j = i + length + 1
            for k in range(i + 1, j):
                cand = table[i][k] + table[k][j] + padded[i] * padded[k] * padded[j]
                if cand > table[i][j]:
                    table[i][j] = cand
    return table[0][n - 1]

cases = [([3, 1, 5, 8], 167), ([1, 5], 10), ([5], 5), ([], 0)]
for coins, expected in cases:
    result = burst_max(coins)
    print("balloons:", coins, "->", result, "expected:", expected, "match:", result == expected)

All four cases pass. Asking about the first burst fails, because its neighbours keep changing as the range empties. The last burst is the only one whose neighbours are known in advance.

Walkthrough: simulating the winning order step by step

The walkthrough replays the winning order for 3, 1, 5, 8. Each step prints the row before the burst. It also prints the two neighbours that set the product.

The first burst removes the 1 while 3 and 5 still flank it. The last burst removes the 8 alone between the two padded ones. Its product is small, and that is fine, because the earlier steps banked the value.

The winning order, burst by burst

row = [3, 1, 5, 8]
order = [1, 5, 3, 8]
total = 0
for value in order:
    idx = row.index(value)
    left = row[idx - 1] if idx > 0 else 1
    right = row[idx + 1] if idx < len(row) - 1 else 1
    gain = left * value * right
    total += gain
    print("row", row, "- burst", value, "between", left, "and", right, "- gain:", gain, "- total:", total)
    row.pop(idx)
print("final total:", total)

The gains are 15, 120, 24 and 8. They sum to the best total of 167. The table from the previous section reaches the same total without replaying any losing order.

Complexity

The table fills one cell per range of the padded row, and each range tries every split point, so its time is O(n cubed) for n balloons. Its space is O(n squared) for the table of ranges.

The brute force simulates n factorial orders. Factorial growth outruns the cubic table very quickly. The counts below put the two side by side.

Orders against range candidates

import math

for n in [4, 6, 8]:
    ranges = n * (n + 1) // 2
    print("balloons", n, "- brute orders:", math.factorial(n), " ranges:", ranges, " split tries per range at most:", n)

At eight balloons the brute force faces 40,320 orders. The table holds 36 ranges. Each range tries a handful of split points, and no order is ever simulated twice.

Edge cases and pitfalls

An empty row earns zero. A single balloon earns its own value, framed by the two padded ones. Both cases fall out of the table with no special code beyond the padding.

The classic pitfall forgets the padding. The first and last balloons then have undefined neighbours. Implementations patch that gap with scattered checks, and one missed check quietly changes the total.

Edge cases, run

def burst_max(coins):
    padded = [1] + coins + [1]
    n = len(padded)
    table = [[0] * n for _ in range(n)]
    for length in range(1, len(coins) + 1):
        for i in range(n - length - 1):
            j = i + length + 1
            for k in range(i + 1, j):
                cand = table[i][k] + table[k][j] + padded[i] * padded[k] * padded[j]
                if cand > table[i][j]:
                    table[i][j] = cand
    return table[0][n - 1]

print("empty row:", burst_max([]))
print("single balloon:", burst_max([5]))
print("two balloons:", burst_max([1, 5]))
print("a zero balloon:", burst_max([0, 5]))
print("all zeros:", burst_max([0, 0, 0]))

The zero balloon row still earns five. Bursting the zero first costs nothing and clears the way. Bursting the five first would earn zero and waste the row.

Exercise

Why does the solution ask which balloon bursts last in a range?

The last balloon is worth the most coins The last balloon's neighbours are the fixed range boundaries The first balloon has no neighbours at all Padding only works for the last balloon