Burst Balloons

HardDynamic Programming · Interval DP🧩 Grid DP LeetCode #312 ↗Updated Oct 30, 2026

Problem

Balloons in a row carry numbers nums[i]. Bursting balloon i earns left × nums[i] × right, where left and right are its current neighbours (a missing neighbour counts as 1); afterwards those neighbours become adjacent. Burst every balloon and return the maximum total coins.

Inputnums = [3,1,5,8]Output167 (3·1·5 + 3·5·8 + 1·3·8 + 1·8·1)

Inputnums = [1,5]Output10

1 ≤ n ≤ 300 · 0 ≤ nums[i] ≤ 100

Try it yourself

Java

class Solution {
    public int maxCoins(int[] nums) {
        
    }
}

Your code is saved in this browser.Submit on LeetCode ↗

Key insight

Choosing the first balloon to burst tangles both sides together. Choose the last balloon k in an open interval (l, r) instead: while it survives, the two sides are independent, and when it finally pops its neighbours are exactly the fixed walls l and r.

PatternGrid DP

Instinct Grid moves that never loop back (right/down, row to row) plus "count or optimise the paths" - build dp[r][c] from the cells that can step in.

Memory hack Every cell asks its parents - a cell's answer comes only from the neighbours that can move into it, so fill cells in the order they arrive.

Open the Grid DP guide →

Approaches

Brute ForceTry Every Bursting Order

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

Simulate the game: at each step pick any remaining balloon, collect its coins from its current neighbours, remove it, and recurse on the shorter row. Put it back afterwards (backtracking). Every permutation of bursts is explored.

Java

public int maxCoins(int[] nums) {
    List<Integer> row = new ArrayList<>();
    for (int x : nums) row.add(x);
    return burstAll(row);
}

private int burstAll(List<Integer> row) {
    int best = 0;
    for (int i = 0; i < row.size(); i++) {
        int left = i > 0 ? row.get(i - 1) : 1;
        int right = i < row.size() - 1 ? row.get(i + 1) : 1;
        int gain = left * row.get(i) * right;
        int removed = row.remove(i);
        best = Math.max(best, gain + burstAll(row));
        row.add(i, removed); // undo
    }
    return best;
}

Faithful to the rules and easy to trust, but factorial — n = 10 is already slow.

BetterMemoized Interval Recursion (Last Balloon)

Time O(n³)Space O(n²)

Pad the row with a 1 on each side. best(l, r) is the most coins from bursting everything strictly between l and r. Try each k as the last one: a[l]·a[k]·a[r] + best(l,k) + best(k,r). There are O(n²) intervals, each scanned in O(n), and the memo solves each once.

Java

public int maxCoins(int[] nums) {
    int n = nums.length;
    int[] a = new int[n + 2];
    a[0] = 1;
    a[n + 1] = 1;
    for (int i = 0; i < n; i++) a[i + 1] = nums[i];
    int[][] memo = new int[n + 2][n + 2];
    for (int[] row : memo) Arrays.fill(row, -1);
    return best(a, 0, n + 1, memo);
}

// max coins for bursting every balloon strictly between l and r
private int best(int[] a, int l, int r, int[][] memo) {
    if (l + 1 == r) return 0; // nothing inside
    if (memo[l][r] != -1) return memo[l][r];
    int res = 0;
    for (int k = l + 1; k < r; k++) {
        int coins = a[l] * a[k] * a[r] + best(a, l, k, memo) + best(a, k, r, memo);
        res = Math.max(res, coins);
    }
    memo[l][r] = res;
    return res;
}

Polynomial and natural to derive; recursion depth is only O(n).

OptimalBottom-Up Interval DP by Length

Time O(n³)Space O(n²)

Fill dp[l][r] for growing gaps r - l, so both halves dp[l][k] and dp[k][r] are always ready. Same recurrence as the memo, but iterative with tight loops and no call overhead.

Java

public int maxCoins(int[] nums) {
    int n = nums.length;
    int[] a = new int[n + 2];
    a[0] = 1;
    a[n + 1] = 1;
    for (int i = 0; i < n; i++) a[i + 1] = nums[i];
    int[][] dp = new int[n + 2][n + 2]; // dp[l][r]: open interval (l, r)
    for (int gap = 2; gap <= n + 1; gap++) {
        for (int l = 0; l + gap <= n + 1; l++) {
            int r = l + gap;
            for (int k = l + 1; k < r; k++) { // k is burst last
                int coins = dp[l][k] + a[l] * a[k] * a[r] + dp[k][r];
                if (coins > dp[l][r]) dp[l][r] = coins;
            }
        }
    }
    return dp[0][n + 1];
}

Same complexity, fastest in practice (~4.5·10⁶ steps at n = 300).

Pro tip

If you get stuck, ask “what if this balloon were the last to go?” — it is the key reframe for many interval DPs.

At a glance

Level	Approach	Time	Space
Brute Force	Try Every Bursting Order	`O(n · n!)`	`O(n)`
Better	Memoized Interval Recursion (Last Balloon)	`O(n³)`	`O(n²)`
Optimal	Bottom-Up Interval DP by Length	`O(n³)`	`O(n²)`

Common pitfalls

Splitting on the first balloon burst — its sub-rows are not independent.
Forgetting the virtual 1s at both ends (and the open-interval meaning of l, r).
Iterating l from left to right without ordering by length — reads unfilled cells.

Interview tips

Show a 3-balloon example where greedy (smallest first) fails before reaching for DP.
Say out loud why “last burst” makes subproblems independent.
Define dp[l][r] precisely (exclusive bounds) before writing any loops.

Pattern

Interval DP → an operation on a range whose cost depends on its current neighbours; fix the last split point.

My notes saved in this browser