Burst Balloons

1. Problem & Core Objective

Each balloon has a number. Bursting balloon i earns nums[i-1] × nums[i] × nums[i+1], where out-of-range neighbours count as 1. After bursting, the neighbours become adjacent. Return the maximum coins obtainable by bursting all balloons.

nums = [3,1,5,8]   →  167
    burst 1: 3*1*5 = 15,  left [3,5,8]
    burst 5: 3*5*8 = 120, left [3,8]
    burst 3: 1*3*8 = 24,  left [8]
    burst 8: 1*8*1 = 8
    total 167

Constraints: 1 <= n <= 300 · 0 <= nums[i] <= 100

What's actually being tested: that asking "which balloon do I burst first?" produces subproblems that aren't independent, and asking "which is burst last?" makes them independent. It's the hardest reframe in the section, and the technique — interval DP — is what it exists to teach.

2. First-Principles Thought Process

Why the forward question fails

Suppose you burst balloon k first in the range (i, j). The range splits into (i, k) and (k, j) — but those halves are not independent, because after everything in the left half is gone, the right half's balloons see new left-neighbours.

The two subproblems interact, so they can't be solved separately. The DP has nowhere to go.

Why the backward question works

Ask instead: which balloon is burst last in this range?

If k is last, then by the time it bursts, everything else in (i, j) is gone — so its neighbours are exactly i and j, the range's fixed boundaries. Its coins are nums[i] × nums[k] × nums[j], known immediately.

And now the halves are independent: (i, k) is fully burst before k, and (k, j) likewise, and neither affects the other's boundaries because i, k, j are all still present while each half is being cleared.

That's the reframe: the last balloon's neighbours are fixed by the interval, whereas the first balloon's neighbours change as its neighbours vanish.

The recurrence

dp[i][j] = max over k strictly between i and j of
           nums[i] * nums[k] * nums[j] + dp[i][k] + dp[k][j]

where dp[i][j] is the best coins from bursting everything strictly between i and j, leaving i and j intact.

The padding

Out-of-range neighbours count as 1, so pad the array with a 1 at each end:

int[] balloons = new int[n + 2];
balloons[0] = balloons[n + 1] = 1;

Then every interval has real boundaries and there are no edge cases.

The fill order

dp[i][j] reads dp[i][k] and dp[k][j] — both shorter intervals. So iterate by increasing interval length, exactly as in the palindrome table.

Complexity

O(n²) intervals × O(n) split points = O(n³). At n = 300 that's 2.7 × 10^7 — fine.

3. Solution Paths

Approach 1 — Try every burst order (brute force)

public int maxCoins(int[] nums) {
    List<Integer> balloons = new ArrayList<>();
    for (int n : nums) balloons.add(n);
    return burst(balloons);
}

private int burst(List<Integer> b) {
    if (b.isEmpty()) return 0;
    int best = 0;

    for (int i = 0; i < b.size(); i++) {
        int left  = i > 0 ? b.get(i - 1) : 1;
        int right = i < b.size() - 1 ? b.get(i + 1) : 1;
        int coins = left * b.get(i) * right;

        int removed = b.remove(i);                   // burst it
        best = Math.max(best, coins + burst(b));
        b.add(i, removed);                            // un-burst
    }
    return best;
}

• Time O(n!) · Space O(n)

Counter-questions on this approach

⭐ "Why n! rather than 2^n?"

Because it's an ordering problem, not a subset problem. Every permutation of burst order is a distinct candidate — n choices, then n−1, and so on.

At n = 300 that's beyond any description. Even n = 12 would be 479 million.

⭐ "Why can't this be memoised on the range, like other interval problems?"

Because the state isn't a range — it's the set of remaining balloons, and there are 2^n of those. Two different removal sequences can leave the same set, but a contiguous range isn't enough to describe it.

That's exactly the problem the backward reframe solves: by fixing the last balloon, the remaining work is describable by two contiguous ranges.

"Is the list manipulation the bottleneck?"

remove(i) and add(i, x) are each O(n) on an ArrayList, adding a factor. But that's irrelevant next to n!.

Approach 2 — Interval DP, thinking backwards (optimal)

public int maxCoins(int[] nums) {
    int n = nums.length;
    int[] balloons = new int[n + 2];
    balloons[0] = balloons[n + 1] = 1;               // padding: out-of-range counts as 1
    for (int i = 0; i < n; i++) balloons[i + 1] = nums[i];

    int[][] dp = new int[n + 2][n + 2];              // dp[i][j] = best for the OPEN interval (i,j)

    for (int len = 2; len <= n + 1; len++)           // by increasing interval width
        for (int i = 0; i + len <= n + 1; i++) {
            int j = i + len;

            for (int k = i + 1; k < j; k++)          // k is burst LAST in (i, j)
                dp[i][j] = Math.max(dp[i][j],
                    balloons[i] * balloons[k] * balloons[j] + dp[i][k] + dp[k][j]);
        }

    return dp[0][n + 1];
}

Trace — nums = [3,1,5,8], padded to [1,3,1,5,8,1]:

The final answer is dp[0][5], which tries each k in 1..4 as the last balloon burst:

Bursting 8 last gives 8 + 159 = 167, matching the example's order.

• Time O(n³) = 2.7 × 10^7 · Space O(n²)

Counter-questions on this approach

⭐ "Why does thinking about the LAST balloon make the subproblems independent?"

If k is burst last in the open interval (i, j), then when it bursts, every other balloon in that interval is already gone — so its neighbours are exactly i and j. Those are the interval's boundaries, which are fixed and still present.

So k's coins are nums[i] × nums[k] × nums[j], computable immediately.

And the two halves (i, k) and (k, j) never interact: while the left half is being cleared, k is still there as its right boundary; while the right half is cleared, k is still there as its left boundary. Neither half's balloons ever see the other half's.

With "first" instead, bursting k immediately makes i and j's relationship change for everything that follows — the halves become adjacent and interfere.

⭐ "Why is dp[i][j] defined on an OPEN interval?"

Because i and j are the surviving boundaries, not balloons to burst. dp[i][j] covers everything strictly between them.

That's what makes dp[i][k] + dp[k][j] correct — the two sub-intervals share k as a boundary, and k isn't double-counted because it's burst separately, by the nums[i]*nums[k]*nums[j] term.

If the interval were closed, k would appear in both halves and be counted twice.

⭐ "Why the padding with 1s?"

The problem says out-of-range neighbours count as 1. Padding makes that literal, so every interval has real boundaries and no special case is needed for the array's ends.

Without it, dp[0][j] would need a branch for "no left neighbour", and so would the right end — four extra cases that the padding eliminates.

⭐ "Why iterate by interval length?"

Because dp[i][j] reads dp[i][k] and dp[k][j], both of which are strictly shorter intervals — since i < k < j. Filling by increasing length guarantees they're ready.

Iterating i and j in the natural nested order would read cells not yet computed. It's the same dependency structure as the palindrome table in Longest Palindromic Substring.

"Why does len start at 2?"

Because an interval of width 1 — j = i + 1 — has nothing strictly between i and j, so dp[i][i+1] = 0, which is the array's default. Width 2 is the first with a balloon inside.

"Could the total overflow?"

Values up to 100 with 300 balloons: each burst earns at most 100³ = 10^6, and there are 300 bursts, so the total is at most 3 × 10^8. Inside int, but not by a huge margin — worth checking rather than assuming.

"Can this be rolled to less space?"

No. dp[i][j] reads a whole range of k, so the table isn't a fixed-window recurrence. O(n²) = 90,000 ints is the floor, which is fine.

That's the general property of interval DPs: they never roll.

Comparison

4. Why the Optimal Wins

The brute force is O(n!) because the state is the set of remaining balloons — 2^n possibilities, unreachable by a range-indexed table.

The reframe from "first" to "last" is what makes the state a contiguous interval. Once k is fixed as the last burst, its neighbours are the interval's boundaries, and the two halves are genuinely independent subproblems.

The framing worth keeping:

Bursting first makes the neighbours unknowable; bursting last makes them the interval's fixed boundaries. dp[i][j] is the open interval (i,j), and the answer is nums[i]*nums[k]*nums[j] + dp[i][k] + dp[k][j] maximised over k.

Plus the two mechanics: pad with 1s so every interval has boundaries, and iterate by increasing length because both sub-intervals are shorter.

5. Java Prerequisites

Padding

int[] balloons = new int[n + 2];
balloons[0] = balloons[n + 1] = 1;

Interval DP loop structure

for (int len = 2; len <= n + 1; len++)          // increasing width
    for (int i = 0; i + len <= n + 1; i++) {
        int j = i + len;
        for (int k = i + 1; k < j; k++)          // k burst LAST
            dp[i][j] = Math.max(dp[i][j],
                balloons[i]*balloons[k]*balloons[j] + dp[i][k] + dp[k][j]);
    }

Open intervals — dp[i][j] excludes both endpoints, which is why dp[i][k] + dp[k][j] doesn't double-count k.

Interval DPs never roll — the recurrence reads a whole range, not a fixed window.

6. Interview Communication Guide

Clarifying questions: Do out-of-range neighbours count as 1 (yes)? Must all balloons be burst (yes)? Can values be 0 (yes — bursting a 0 earns nothing but still removes it)? What's n (300, so O(n³) is fine)?

The pitch

"The natural question — 'which balloon do I burst first?' — doesn't work, and seeing why is the whole problem.

If I burst k first in a range, the range splits into two halves. But those halves aren't independent: once the left half is gone, the right half's balloons have new left-neighbours. They interact, so I can't solve them separately.

The fix is to ask which balloon is burst last.

If k is last in the open interval (i, j), then by the time it bursts everything else in that interval is gone — so its neighbours are exactly i and j, the interval's fixed boundaries. Its coins are nums[i] × nums[k] × nums[j], known immediately.

And now the halves genuinely are independent: while the left half is being cleared, k is still standing as its right boundary, and vice versa. Neither half ever sees the other.

So dp[i][j] = max over k of nums[i]*nums[k]*nums[j] + dp[i][k] + dp[k][j], where dp[i][j] covers everything strictly between i and j. Defining it on an open interval is what stops k being double-counted — it appears as a boundary in both halves but is burst by the product term.

Two mechanics. I pad the array with 1s at both ends, so out-of-range neighbours are literal and no edge case is needed. And I iterate by increasing interval length, because both sub-intervals are strictly shorter.

O(n³) — n² intervals times n split points — which is 2.7 × 10^7 here. O(n²) space, and interval DPs never roll, because the recurrence reads a whole range rather than a fixed window.

The brute force is O(n!), not 2^n, because it's an ordering problem. And it can't be memoised on a range, since its state is the set of remaining balloons — which is precisely what the backward reframe fixes."

Edge cases to volunteer:

Name [1]. With padding it's 1 × 1 × 1 = 1, and it confirms the boundaries are handled — a solution without padding would need a special case and often returns 0.

7. Follow-Up Questions — Modified Constraints

⭐ "Return the burst order, not just the total."

Record which k won for each interval, then reconstruct recursively: k is burst last in (i,j), so recurse into (i,k) and (k,j) first and append k. O(n²) extra space.

⭐ "What if bursting a balloon earned only nums[i-1] × nums[i+1], without itself?"

The same interval DP with a different product term. The structure is entirely about which balloon is last, not about the specific reward — which shows the reframe is the transferable part.

"What if you could only burst k balloons, not all of them?"

Add a dimension for the count remaining: dp[i][j][c]. O(n³ · k) time. Feasible for small k, expensive otherwise.

"What if n were 1000?"

O(n³) = 10^9 — too slow. There's no known sub-cubic algorithm for this. The Knuth-Yao optimisation speeds up some interval DPs to O(n²) when the cost function satisfies the quadrangle inequality, but this one doesn't.

"What other problems use this interval DP shape?"

Matrix Chain Multiplication — which associative split is done last. Optimal Binary Search Tree — which key is the root. Both share the "fix the final/topmost choice, then the halves are independent" structure.

Recognising that family is worth more than the specific recurrence.

"What if the balloons were in a circle?"

Then there are no fixed boundaries to pad, and the case-split trick from House Robber II doesn't apply cleanly either. You'd typically duplicate the array and constrain the interval length, at O((2n)³).