Burst Balloons

+10

A row of balloons is given as nums, where nums[i] is the number on balloon i. You burst all of them, one at a time, in any order you choose. Bursting a balloon earns left × nums[i] × right coins, where left and right are the numbers on its current neighbours: the nearest balloons on each side that are still in the row. A missing neighbour, past either end of the row, counts as 1. After a burst, the two neighbours become adjacent. Return the most coins you can collect.

Function

maxCoins(nums: integer-array) → integer

numsinteger-array: the numbers on the balloons, from left to right
Returnsinteger: the most coins you can collect by bursting every balloon

Constraints

1 ≤ nums.length ≤ 300
0 ≤ nums[i] ≤ 100
The answer is below 3 × 10⁸, so it fits in a 32-bit signed integer.

Examples

Input: nums = [2, 4, 3]
Output: 33
Explanation: Burst the 4 first for 2 × 4 × 3 = 24 coins. The 2 and the 3 are now neighbours, so bursting the 2 earns 1 × 2 × 3 = 6, and the 3, now alone, earns 1 × 3 × 1 = 3. That makes 33, and no other order does better: bursting the small 2 first already caps you at 24.

+15 hidden tests on Submit

Follow-up

Can you also return one bursting order that earns the most coins?

Hints

Open them one at a time. Each one gives away a little more.

0 of 3 opened

Solution

Every burst changes who is next to whom, so a choice now changes the price of every later burst. Trying all orders means n! sequences. Thinking about the first balloon to burst does not split the row either, because its two sides become neighbours. Thinking about the last balloon to burst in a stretch does: it stays in place while everything else goes, so the stretch on its left and the stretch on its right are independent. An interval table over those stretches solves the problem in O(n³).

Try every bursting order

Correct, but does not finish on the largest tests

Intuition

Pick any balloon to burst now, collect left × value × right with its current neighbours, remove it from the row, and solve the shorter row the same way. Do that for every choice and keep the best total. A recursive function burstAll(row) does exactly this. It explores every possible order, so the answer is right.

It is hopeless for real sizes. The first burst has n choices, the second n-1, and so on: n! orders. For 12 balloons that is already 479,001,600 orders, and the largest test has 120 balloons. Remembering results for each set of balloons still standing does not rescue it, because there are 2^n such sets.

The way out is to notice why the subproblems are so many. After you burst balloon k, the balloon on its left and the one on its right touch, so what happens on the left still depends on the right. The next approach picks the balloon to think about so that the two sides stop affecting each other.

Algorithm

Write burstAll(row), which returns the most coins from the balloons in row.
For each position k, read the neighbours, using 1 past either end.
Earn left × row[k] × right, and add burstAll of the row without row[k].
Return the best total over all k, or 0 for an empty row.
Call burstAll(nums).

def maxCoins(nums):
    # Most coins you can still collect from the balloons in row
    def burst_all(row):
        top = 0
        for k in range(len(row)):
            left = row[k - 1] if k > 0 else 1
            right = row[k + 1] if k + 1 < len(row) else 1
            # Burst row[k] now, then do as well as possible with the rest
            coins = left * row[k] * right + burst_all(row[:k] + row[k + 1:])
            top = max(top, coins)
        return top

    return burst_all(nums)

Recursion on the last balloon, with a memo

Intuition

First, put a 1 at both ends: vals = [1] + nums + [1]. These two never burst, and they stand for the missing neighbours at the edges. Now look at a gap between two positions left and right that are both still standing, and ask: which balloon inside the gap bursts last?

Say it is k. While the other balloons in the gap burst, k is still there, standing between them like a wall. Every balloon between left and k has neighbours from that stretch only, with left and k as fixed borders, and the same holds between k and right. So the two stretches are independent problems of the same kind. When k finally bursts, everything between the borders is gone, so its neighbours are exactly left and right, and it earns vals[left] × vals[k] × vals[right]. Choosing the first balloon gives no such split, because its two sides become neighbours.

That gives a recursion. solve(left, right) returns the most coins from the balloons strictly between left and right: 0 when the gap is empty, otherwise the largest solve(left, k) + solve(k, right) + vals[left] × vals[k] × vals[right] over every k in the gap. The answer is solve(0, m-1), the gap between the two pads.

On its own the recursion meets the same gap again and again, so store each result in a table memo[left][right] and return it on the next visit. There are about n²/2 gaps, each tries up to n balloons, so the work is O(n³). Use -1 for a gap not solved yet, because 0 is a real answer. The recursion never goes deeper than n+1 calls, since every call works on a narrower gap.

Algorithm

Build vals as nums with a 1 added at each end, and set m to its length.
Make an m × m memo filled with -1.
Write solve(left, right): return 0 if right - left < 2, and the stored value if there is one.
Otherwise try every k strictly between them as the last balloon, keep the largest solve(left, k) + solve(k, right) + vals[left] × vals[k] × vals[right], and store it.
Return solve(0, m-1).

def maxCoins(nums):
    # A 1 on each side stands for the ends of the row
    vals = [1] + nums + [1]
    m = len(vals)
    memo = [[-1] * m for _ in range(m)]

    # Most coins from the balloons strictly between left and right
    def solve(left, right):
        if right - left < 2:
            return 0
        if memo[left][right] >= 0:
            return memo[left][right]
        top = 0
        for last in range(left + 1, right):
            # last bursts after every other balloon in the gap
            coins = solve(left, last) + solve(last, right) + vals[left] * vals[last] * vals[right]
            top = max(top, coins)
        memo[left][right] = top
        return top

    return solve(0, m - 1)

Fill the interval table by width

Intuition

The recursion only ever asks about narrower gaps. So you can fill the same table without recursion, as long as you fill narrow gaps before wide ones. Let best[left][right] be the most coins from the balloons strictly between left and right, 0 for a gap with nothing inside. For each width from 2 up, and each gap of that width, try every k inside as the last balloon. best[left][k] and best[k][right] are narrower, so they are already final.

Take [2, 4, 3]. Padded, it is vals = [1, 2, 4, 3, 1] at positions 0 to 4, and the answer is best[0][4]. Fill the gaps from the narrowest up:

Width 2, one balloon inside: best[0][2] = 1 × 2 × 4 = 8, best[1][3] = 2 × 4 × 3 = 24, best[2][4] = 4 × 3 × 1 = 12.
best[0][3], balloons 2 and 4: the 2 last gives 0 + 24 + 1 × 2 × 3 = 30; the 4 last gives 8 + 0 + 1 × 4 × 3 = 20. So 30.
best[1][4], balloons 4 and 3: the 4 last gives 0 + 12 + 2 × 4 × 1 = 20; the 3 last gives 24 + 0 + 2 × 3 × 1 = 30. So 30.
best[0][4], all three: the 2 last gives 0 + 30 + 1 × 2 × 1 = 32; the 4 last gives 8 + 12 + 1 × 4 × 1 = 24; the 3 last gives 30 + 0 + 1 × 3 × 1 = 33. So 33.

Read the winning choices back and you get the order: the 3 goes last, before it the 2 is last of the stretch to its left, and the 4 goes first. That is 24 + 6 + 3 = 33.

The work is the same as with the memo: 302 × 301 × 300 / 6 ≈ 4.5 × 10^6 steps for 300 balloons, and a table of 302 × 302 numbers. Plain loops avoid millions of function calls, which makes this version several times faster than the recursion in a language such as Python or R.

Algorithm

Build vals as nums with a 1 added at each end, and set m to its length.
Make an m × m table best filled with 0.
For each width from 2 to m-1, and each left with right = left + width inside the array, try every k strictly between them.
Set best[left][right] to the largest best[left][k] + best[k][right] + vals[left] × vals[k] × vals[right].
Return best[0][m-1].

def maxCoins(nums):
    # A 1 on each side stands for the ends of the row
    vals = [1] + nums + [1]
    m = len(vals)
    # best[left][right]: most coins from the balloons strictly between left and right
    best = [[0] * m for _ in range(m)]
    for width in range(2, m):
        for left in range(m - width):
            right = left + width
            edge = vals[left] * vals[right]
            top = 0
            for last in range(left + 1, right):
                # last goes after every other balloon in the gap,
                # so left and right are its neighbours when it bursts
                coins = best[left][last] + best[last][right] + edge * vals[last]
                if coins > top:
                    top = coins
            best[left][right] = top
    return best[0][m - 1]

Pitfalls and edge cases

The usual mistakes are a greedy order, a recursion on the first burst, a bad memo marker, and a table filled in the wrong order.

Greedy orders fail. Bursting the smallest balloon first earns 24 on [2, 4, 3] instead of 33, and bursting the balloon that pays the most right now earns 42 on [2, 9, 2], while bursting a 2 first earns 18 + 18 + 9 = 45.
Splitting on the first burst with its original neighbours, nums[k-1] × nums[k] × nums[k+1] plus the two sides, counts neighbours that may already be gone. On [2, 4, 3] it reports 44, more than any real order earns.
Counting the borders as part of the gap. left and right are still standing when the gap is cleared; only the balloons strictly between them burst.
Filling the table row by row with left going up. Then best[k][right] for k > left is not computed yet and reads as 0. Fill by width, or walk left downward.
Marking an unsolved gap in the memo with 0. A gap full of zero balloons really is worth 0, so it looks unsolved forever and is solved again on every visit. Use -1.
Forgetting the two padding 1s, which leaves the end balloons with no neighbour to multiply by.
In Lua and R the padded positions run from 1 to m, so the answer is best[1][m].

Frequently asked questions4

Why does Burst Balloons pick the last balloon instead of the first?

After the first burst, the balloons on its two sides become neighbours, so the left part and the right part still affect each other and cannot be solved separately. The last balloon of a stretch stays in place while the others burst, so the two sides never meet, and when it goes its neighbours are the stretch's fixed borders. That makes each stretch an independent subproblem, which is what dynamic programming needs.

What is the time complexity of Burst Balloons?

The interval table has about n²/2 gaps, and each tries up to n balloons as the last one, so the time is O(n³) and the memory O(n²). For 300 balloons that is about 4.5 × 10^6 steps. Trying every order is O(n · n!).

Can Burst Balloons be solved with a greedy order?

No. Every simple rule fails on a small row. Bursting the smallest balloon first earns 24 on [2, 4, 3], where 33 is possible. Bursting the balloon that pays the most right now earns 42 on [2, 9, 2], where bursting a 2 first earns 45. A burst changes the prices of the later ones, so you need the dynamic programming over gaps.

Why add a 1 at both ends of the array?

A missing neighbour counts as 1, so two padding balloons with value 1 that never burst give every real balloon two neighbours without special cases. They also serve as the borders of the whole problem: the answer is the gap between the two pads, best[0][m-1].

Python

def maxCoins(nums):
    # Write code here

Test cases

Case 1

Case 2

Case 3

Input

nums = [2, 4, 3]

Expected

Burst Balloons

Function

Constraints

Examples

Hints

Solution

Try every bursting order

Recursion on the last balloon, with a memo

Fill the interval table by width

Pitfalls and edge cases

Frequently asked questions4

Similar problems